3-Coloring graphs embedded in surfaces

DOI10.1002/(SICI)1097-0118(200003)33:3%3C140::AID-JGT3%3E3.0.CO;2-3MaRDI QIDQ4948508zbMATH OpenOpenAlexFDO

Authors Yue Zhao

Publication date 11 April 2000

Full work available at URL https://doi.org/10.1002/(sici)1097-0118(200003)33:3%3C140::aid-jgt3%3E3.0.co;2-3

zbMATH Keywords

3-coloringsurfacevertex coloring

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Review text

P. Erdős (1990) raised the following question which is a relaxation of R. Steinberg's conjecture: Is there an integer \(k\geq 5\) such that, if \(G\) is a planar graph without \(i\)-circuits, \(4\leq i\leq k\), then \(G\) is 3-colorable? In this paper, the author proves that for any surface \(\Sigma\), there exists an integer \(k(\Sigma)\geq 5\) such that, if \(G\) is a graph embedded in \(\Sigma\) without \(i\)-circuits, \(4\leq i\leq k(\Sigma)\), then \(G\) is 3-colorable. This result extends some earlier results on Erdős' question obtained by H. L. Abbott and B. Zhou (1991), D. P. Sanders and the author (1995) as well as O. V. Borodin (1996).

Recommendations

• A note on the three color problem
• Planar graphs without 4, 6, 8-cycles are 3-colorable
• Three-coloring graphs embedded on surfaces with all faces even-sided
• Planar graphs without cycles of length from 4 to 7 are 3-colorable

Cited in

(7)

• A structural theorem on embedded graphs and its application to colorings
• Three-coloring graphs embedded on surfaces with all faces even-sided
• Coloring drawings of graphs
• On the Total Coloring of Graphs Embeddable in Surfaces
• scientific article; zbMATH DE number 7145382 (Why is no real title available?)
• The last excluded case of Dirac's map‐color theorem for choosability
• 3-regular maps on closed surfaces are nearly distinguishing 3-colorable with few exceptions

This page was built for publication: 3-Coloring graphs embedded in surfaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4948508)