Polyhedral embeddings of snarks in orientable surfaces

Kochol, Martin

doi:10.1090/S0002-9939-08-09698-6

Polyhedral embeddings of snarks in orientable surfaces
HTML articles powered by AMS MathViewer

by Martin Kochol PDF

Proc. Amer. Math. Soc. 137 (2009), 1613-1619 Request permission

Abstract:

An embedding of a 3-regular graph in a surface is called polyhedral if its dual is a simple graph. An old graph-coloring conjecture is that every 3-regular graph with a polyhedral embedding in an orientable surface has a 3-edge-coloring. An affirmative solution of this problem would generalize the dual form of the Four Color Theorem to every orientable surface. In this paper we present a negative solution to the conjecture, showing that for each orientable surface of genus at least 5, there exist infinitely many 3-regular non-3-edge-colorable graphs with a polyhedral embedding in the surface.

References

M.O. Albertson, H. Alpert, S.-M. Belcastro, R. Haas, Grünbaum colorings of toroidal triangulations, 2008, manuscript.
Kenneth Appel and Wolfgang Haken, Every planar map is four colorable, Contemporary Mathematics, vol. 98, American Mathematical Society, Providence, RI, 1989. With the collaboration of J. Koch. MR 1025335, DOI 10.1090/conm/098
D. Archdeacon, Problems in topological graph theory: Three-edge-coloring orientable triangulations, http://www.emba.uvm.edu/$\tilde {\phantom {a}}$archdeac/problems/grunbaum.htm.
sarah-marie Belcastro and Jackie Kaminski, Families of dot-product snarks on orientable surfaces of low genus, Graphs Combin. 23 (2007), no. 3, 229–240. MR 2320577, DOI 10.1007/s00373-007-0729-9
Reinhard Diestel, Graph theory, 3rd ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Berlin, 2005. MR 2159259
Jonathan L. Gross and Thomas W. Tucker, Topological graph theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1987. A Wiley-Interscience Publication. MR 898434
W. T. Tutte (ed.), Recent progress in combinatorics, Academic Press, New York-London, 1969. MR 0250896
Martin Kochol, Snarks without small cycles, J. Combin. Theory Ser. B 67 (1996), no. 1, 34–47. MR 1385382, DOI 10.1006/jctb.1996.0032
Martin Kochol, Superposition and constructions of graphs without nowhere-zero $k$-flows, European J. Combin. 23 (2002), no. 3, 281–306. MR 1908651, DOI 10.1006/eujc.2001.0563
P.G. Tait, Remarks on the colouring of maps, Proc. Roy. Soc. Edinburgh 10 (1880), 729.