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.
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
DefinitionsWe start with definition, for pictures please download my presentation.
Planar cubic graph
We call a graph
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.
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?