We study critical graphs on surfaces. A graph G is said to be k-critical if G is k-chromatic and every proper subgraph of G is (k-1)-colorable. It is known that there are finitely many k-critical graphs on any surface for k at least 6 and infinitely many k-critical graphs for k at least 5 for all surfaces except for the plane. By Divac's theorem, the only projective planar 6-critical graph is the complete graph of order six. Thomassen exhibited the list of all toroidal 6-critical graph and conjectured that there are only four 6-critical graphs embedable in the Klein bottle. We refutate this conjecture and find a complete list of nine 6-critical graphs embedable in the Klein bottle. The same result using a different method was independently obtained by N. Chenette, L. Postle, N. Streib, R. Thomas and C. Yerger. Our proof is based on generating all 6-critical graphs on Klein bottle from K_6 in a systematic way. By Euler's formula, every 6-critical graph on the Klein bottle is 6-regular or contains a vertex of degree 5. All such 6-regular graphs are 5-colorable. The main idea of our proof is reversing the following reduction procedure: Consider a vertex v of degree 5 in a 6-critical graph G. If every pair of its neighbors is adjacent, then G is K_6. Otherwise, there are two nonadjacent neighbors and we can contract them into a new vertex. The resulting graph is not 5-colorable and thus it must contain 6-critical subgraph with the contracted vertex.
joint work with Ken-ichi Kawarabayashi, Daniel Kral' and Jan Kync
This research was conducted during Research Experience for
Undergraduates (REU) 2007 at DIMACS, Rutgers University.