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, Heraklion, Crete, Greece , 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
ID Code:918

Repository Staff Only: item control page

References

Albertson, M.O., Alpert, H., Belcastro, S.-M., Haas, R.: Grünbaum colorings of toroidal triangulations. (April 2008), (manuscript).

Appel, K., Haken, W.: Every Planar Map Is Four Colorable. Contemp. Math., vol. 98. Amer. Math. Soc., Providence, RI (1989).

Archdeacon, D.: Problems in topological graph theory: Three-edge-coloring planar triangulations. http://www.emba.uvm.edu/∼archdeac/problems/grunbaum.htm

Belcastro, S.-M., Kaminski,J.: Families of dot-product snarks on orientable surfaces of low genus. Graphs Combin. 23, 229–240 (2007).

Diestel, R.: Graph Theory, 3rd ed. Springer-Verlag, Heidelberg (2005).

Gross, J.L., Tuker, T.W.: Topological Graph Theory. Wiley, New York (1987).

Grünbaum, B.: Conjecture 6. In: Tutte, W.T. (ed.) Recent Progress in Combinatorics, Proceedings of the Third Waterloo Conference on Combinatorics, May 1968. p. 343. Academic Press, New York (1969).

Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10, 718–720 (1981).

Kochol, M.: Snarks without small cycles. J. Combin. Theory Ser. B 67, 34–47 (1996).

Kochol, M.: Superposition and constructions of graphs without nowhere-zero k-flows. European J. Combin. 23, 281–306 (2002).

Tait, P.G.: Remarks on the colouring of maps. Proc. Roy. Soc. Edinburgh 10, 729 (1880).

Vodopivec, A.: On embedding of snarks in the torus. Discrete Math. 308, 1847–1849 (2008).