|
Polyhedral embeddings of snarks in orientable surfaces
Author(s):
Martin
Kochol
Journal:
Proc. Amer. Math. Soc.
137
(2009),
1613-1619.
MSC (2000):
Primary 05C15, 05C10
Posted:
November 14, 2008
MathSciNet review:
2470819
Retrieve article in:
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.
References:
-
- 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.
Similar Articles:
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é myto 19, 811 03 Bratislava 1, Slovakia
Email:
kochol@savba.sk
DOI:
10.1090/S0002-9939-08-09698-6
PII:
S 0002-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
Posted:
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
Copyright of article:
Copyright
2008,
American Mathematical Society
|
