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.

Our advisor is Aaron Jaggard.

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?