Polyhedral embeddings of snarks in orientable surfaces

Author:
Martin Kochol

Journal:
Proc. Amer. Math. Soc. **137** (2009), 1613-1619

MSC (2000):
Primary 05C15, 05C10

DOI:
https://doi.org/10.1090/S0002-9939-08-09698-6

Published electronically:
November 14, 2008

MathSciNet review:
2470819

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

**1.**M.O. Albertson, H. Alpert, S.-M. Belcastro, R. Haas,*Grünbaum colorings of toroidal triangulations*, 2008, manuscript.**2.**K. Appel, W. Haken,*Every Planar Map Is Four Colorable*, Contemp. Math., vol. 98, Amer. Math. Soc., Providence, RI, 1989. MR**1025335 (91m:05079)****3.**D. Archdeacon,*Problems in topological graph theory: Three-edge-coloring orientable triangulations*,`http://www.emba.uvm.edu/ archdeac/problems/ grunbaum.htm`.**4.**S.-M. Belcastro, J. Kaminski,*Families of dot-product snarks on orientable surfaces of low genus*, Graphs Combin.**23**(2007), 229-240. MR**2320577 (2008e:05040)****5.**R. Diestel,*Graph Theory*, 3rd ed., Springer-Verlag, Berlin-Heidelberg, 2005. MR**2159259 (2006e:05001)****6.**J.L. Gross, T.W. Tucker,*Topological Graph Theory*, Wiley, New York, 1987. MR**898434 (88h:05034)****7.**B. Grünbaum,*Conjecture 6*, Recent Progress in Combinatorics, Proceedings of the Third Waterloo Conference on Combinatorics, May 1968, W.T. Tutte (ed.), Academic Press, New York, 1969, p. 343. MR**0250896 (40:4128)****8.**M. Kochol,*Snarks without small cycles*, J. Combin. Theory Ser. B**67**(1996), 34-47. MR**1385382 (97d:05114)****9.**M. Kochol,*Superposition and constructions of graphs without nowhere-zero -flows*, European J. Combin.**23**(2002), 281-306. MR**1908651 (2003d:05172)****10.**P.G. Tait,*Remarks on the colouring of maps*, Proc. Roy. Soc. Edinburgh**10**(1880), 729.

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC (2000):
05C15,
05C10

Retrieve articles in all journals with MSC (2000): 05C15, 05C10

Additional Information

**Martin Kochol**

Affiliation:
Suché mýto 19, 811 03 Bratislava 1, Slovakia

Email:
kochol@savba.sk

DOI:
https://doi.org/10.1090/S0002-9939-08-09698-6

Keywords:
Edge-coloring,
orientable surface,
polyhedral embedding,
snark,
nowhere-zero flow,
dual of a graph

Received by editor(s):
December 20, 2007

Received by editor(s) in revised form:
July 11, 2008

Published electronically:
November 14, 2008

Additional Notes:
This work was supported by an Alexander von Humboldt Fellowship and by grant VEGA 2/7037/7

Communicated by:
Jim Haglund

Article copyright:
© Copyright 2008
American Mathematical Society