Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk

DOI10.1016/j.jctb.2018.03.001zbMath1391.05106arXiv1302.2158OpenAlexW2963391555WikidataQ130051482 ScholiaQ130051482MaRDI QIDQ723878

Zdeněk Dvořák, Robin Thomas, Daniel Král'

Publication date: 24 July 2018

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1302.2158

zbMATH Keywords

planar graphscritical graphs3-coloringgirth five

Mathematics Subject Classification ID

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

Related Items (7)

Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle. ⋮ Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm ⋮ Characterization of 4-critical triangle-free toroidal graphs ⋮ Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five ⋮ 3-list-coloring graphs of girth at least five on surfaces ⋮ Coloring near-quadrangulations of the cylinder and the torus ⋮ Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs

Cites Work

• Unnamed Item
• Ore's conjecture for \(k=4\) and Grötzsch's theorem
• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• The chromatic number of a graph of girth 5 on a fixed surface
• A short list color proof of Grötzsch's theorem
• Three-coloring Klein bottle graphs of girth five
• 3-list-coloring planar graphs of girth 5
• Three-coloring triangle-free planar graphs in linear time
• Coloring graphs with fixed genus and girth
• 4-chromatic projective graphs
• On a conjecture of B. Grünbaum

This page was built for publication: Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk