Fine Structure of 4-Critical Triangle-Free Graphs II. Planar Triangle-Free Graphs with Two Precolored 4-Cycles

DOI10.1137/15M1023397zbMath1366.05041arXiv1505.07296OpenAlexW2172252798MaRDI QIDQ5346562

Zdeněk Dvořák, Bernard Lidický

Publication date: 24 May 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

planar graphscritical graphs3-coloringprecoloring

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15)

Related Items

Triangle-free planar graphs with small independence number ⋮ Fine Structure of 4-Critical Triangle-Free Graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains ⋮ Do triangle-free planar graphs have exponentially many 3-colorings? ⋮ Flexibility of triangle‐free planar graphs ⋮ Fine Structure of 4-Critical Triangle-Free Graphs III. General Surfaces ⋮ Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies ⋮ Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles

Cites Work

• Planar 4-critical graphs with four triangles
• Many 3-colorings of triangle-free planar graphs
• 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
• Three-coloring Klein bottle graphs of girth five
• Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies
• Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs
• Fine Structure of 4-Critical Triangle-Free Graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains
• Coloring graphs with fixed genus and girth
• 4-Critical Graphs on Surfaces Without Contractible $(\le\!4)$-Cycles