Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs

DOI10.1016/j.jctb.2020.09.001OpenAlexW3084481792MaRDI QIDQ2040021

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

Publication date: 6 July 2021

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

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

zbMATH Keywords

graph coloringtriangle-freegraphs on surfaces

Mathematics Subject Classification ID

Theory of computing (68Qxx) Graph theory (05Cxx)

Related Items (6)

Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm ⋮ Characterization of 4-critical triangle-free toroidal graphs ⋮ 3-Coloring Triangle-Free Planar Graphs with a Precolored 9-Cycle ⋮ Fine Structure of 4-Critical Triangle-Free Graphs II. Planar Triangle-Free Graphs with Two Precolored 4-Cycles ⋮ Fine Structure of 4-Critical Triangle-Free Graphs III. General Surfaces ⋮ Three-coloring triangle-free graphs on surfaces. VI: 3-colorability of quadrangulations

Cites Work

• Unnamed Item
• Ore's conjecture for \(k=4\) and Grötzsch's theorem
• From the plane to higher surfaces
• Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk
• Graph minors. VII: Disjoint paths on a surface
• 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 graphs embedded on surfaces with all faces even-sided
• Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five
• Three-coloring triangle-free planar graphs in linear time
• Coloring graphs with fixed genus and girth
• On a conjecture of B. Grünbaum

This page was built for publication: Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs