Fine structure of 4-critical triangle-free graphs. III: General surfaces

DOI10.1137/15M1023403MaRDI QIDQ4601215zbMATH OpenOpenAlexFDO

Authors Zdeněk Dvořák, Bernard Lidický

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

coloringplanar graphssurfaces

Mathematics Subject Classification ID

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

Abstract: Dvov{r}'ak, Kr'al' and Thomas gave a description of the structure of triangle-free graphs on surfaces with respect to 3-coloring. Their description however contains two substructures (both related to graphs embedded in plane with two precolored cycles) whose coloring properties are not entirely determined. In this paper, we fill these gaps.

Recommendations

• Fine structure of 4-critical triangle-free graphs. II: Planar triangle-free graphs with two precolored 4-cycles
• Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk
• Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs
• Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five
• Fine Structure of 4-Critical Triangle-Free Graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains

Cites work

• Chromatic numbers and cycle parities of quadrangulations on nonorientable closed surfaces
• Coloring graphs with fixed genus and girth
• Coloring locally bipartite graphs on surfaces.
• Fine Structure of 4-Critical Triangle-Free Graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains
• Fine structure of 4-critical triangle-free graphs. II: Planar triangle-free graphs with two precolored 4-cycles
• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• scientific article; zbMATH DE number 3482373 (Why is no real title available?)
• Planar 4-critical graphs with four triangles
• The chromatic number of a graph of girth 5 on a fixed surface
• Three-coloring graphs embedded on surfaces with all faces even-sided
• Three-coloring Klein bottle graphs of girth five
• Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs
• Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies

Cited in

(7)

• Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs
• Coloring near-quadrangulations of the cylinder and the torus
• Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm
• Characterization of 4-critical triangle-free toroidal graphs
• Fine Structure of 4-Critical Triangle-Free Graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains
• scientific article; zbMATH DE number 1420924 (Why is no real title available?)
• \((3a:a)\)-list-colorability of embedded graphs of girth at least five

This page was built for publication: Fine structure of 4-critical triangle-free graphs. III: General surfaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601215)