Fine Structure of 4-Critical Triangle-Free Graphs III. General Surfaces

DOI10.1137/15M1023403zbMath1377.05057arXiv1505.07297OpenAlexW3102197389MaRDI QIDQ4601215

Bernard Lidický, Zdeněk Dvořák

Publication date: 12 January 2018

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

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

zbMATH Keywords

planar graphssurfacescoloring

Mathematics Subject Classification ID

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

Related Items (6)

Fine Structure of 4-Critical Triangle-Free Graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains ⋮ Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm ⋮ Characterization of 4-critical triangle-free toroidal graphs ⋮ $(3a:a)$-List-Colorability of Embedded Graphs of Girth at Least Five ⋮ Coloring near-quadrangulations of the cylinder and the torus ⋮ Irreducible 4-critical triangle-free toroidal graphs

Cites Work

• Unnamed Item
• Planar 4-critical graphs with four triangles
• 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
• Coloring locally bipartite graphs on surfaces.
• Chromatic numbers and cycle parities of quadrangulations on nonorientable closed surfaces
• Three-coloring Klein bottle graphs of girth five
• Three-coloring graphs embedded on surfaces with all faces even-sided
• 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
• Fine Structure of 4-Critical Triangle-Free Graphs II. Planar Triangle-Free Graphs with Two Precolored 4-Cycles

This page was built for publication: Fine Structure of 4-Critical Triangle-Free Graphs III. General Surfaces