3-Regular non 3-Edge-Colorable Graphs with Polyhedral Embeddings in Orientable Surfaces

Kochol, Martin (2009) 3-Regular non 3-Edge-Colorable Graphs with Polyhedral Embeddings in Orientable Surfaces. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008 , pp. 319-335(Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_31).

Full text not available from this repository.

Abstract

The Four Color Theorem is equivalent with its dual form stating that each 2-edge-connected 3-regular planar graph is 3-edgecolorable. In 1968, Grünbaum conjectured that similar property holds true for any orientable surface, namely that each 3-regular graph with a polyhedral embedding in an orientable surface has a 3-edge-coloring. Note that an embedding of a graph in a surface is called polyhedral if its geometric dual has no multiple edges and loops. 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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-00219-9_31
Classifications: G Algorithms and Complexity > G.490 Embeddings
URI: http://gdea.informatik.uni-koeln.de/id/eprint/918

Actions (login required)

View Item View Item