Skip to Main Content

Proceedings of the American Mathematical Society

Published by the American Mathematical Society, the Proceedings of the American Mathematical Society (PROC) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6826 (online) ISSN 0002-9939 (print)

The 2020 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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.
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é mýto 19, 811 03 Bratislava 1, Slovakia
  • Email: kochol@savba.sk
  • 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
  • © Copyright 2008 American Mathematical Society
  • 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
  • MathSciNet review: 2470819