Department of
Applied
Mathematics

Counterexample to the conjecture of Grunbaum

Martin Kochol

MU SAV, Bratislava

Abstract

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.