On 10.11.2009 at 12:20 in corridor, there is the following noon lecture:
Counterexample to the conjecture of Grunbaum
MU SAV, Bratislava
By a classical result of Tait, the four color theorem is equivalent with the statement that each 2-edge-connected 3-regular planar graph has a 3-edge-coloring. An embedding of a graph in a surface is called polyhedral if its dual has no multiple edges and loops. A conjecture of Grunbaum, presented in 1968, states that each 3-regular graph with a polyhedral embedding in an orientable surface has a 3-edge-coloring. With respect to the result of Tait, it aims to generalize the four color theorem for any orientable surface. We present a negative solution of this conjecture, showing that for each orientable surface of genus at least 5, there exists a 3-regular non 3-edge-colorable graph with a polyhedral embedding in the surface.
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010