Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five

DOI10.1016/j.jctb.2020.06.005zbMath1448.05074arXiv1402.4710OpenAlexW3038385145MaRDI QIDQ2200929

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

Publication date: 24 September 2020

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

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

zbMATH Keywords

surfacestriangle-freecoloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items

Hyperbolic families and coloring graphs on surfaces ⋮ Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm ⋮ Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$ ⋮ $(3a:a)$-List-Colorability of Embedded Graphs of Girth at Least Five ⋮ 3-list-coloring graphs of girth at least five on surfaces ⋮ Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle.
• Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk
• 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
• Continuation of a 3-coloring from a 7-face onto a plane graph without \(C_3\)
• Three-coloring triangle-free planar graphs in linear time
• Coloring graphs with fixed genus and girth
• 4-chromatic projective graphs
• 4-Critical Graphs on Surfaces Without Contractible $(\le\!4)$-Cycles
• On a conjecture of B. Grünbaum