# Pavel Klavík

Hello, welcome to my REU page. My name is Pavel Klavík and I am a undergraduate student of Computer Science at the Faculty of Maths and Physics of Charles University in Prague. My main scientific interests are combinatorics and graph theory.

# REU 2009

The other members of our research group are Ondra Bílka, Jozef Jirásek, Pavel Paták, Zuzka Safernová, Martin Tancer and Jan Volec.

## Problems

We are working together on several problems, some of them are described on pages of my colleagues.

### Fair Coloring of Planar Cubic Graphs

#### Definitions

##### Planar cubic graph

We call a graph

• planar if it can be drawn in the plane without crossing, and
• cubic if the degree of all the vertices is three.

##### Coloring and fair coloring

A k-coloring is an assignment of k different colors to the vertices of the graph.

A coloring is proper if no two adjacent vertices have the same color.

Every planar graph has a proper 4-coloring.

A proper 4-coloring of a cubic planar graph is fair if all the neighbors of each vertex have distinct colors.

#### Problem

For a given cubic planar graph we want to decide if there exists a fair coloring of the graph.

How difficult is such problem? Does there exist an efficient algorithm?