The chromatic number of a graph of girth 5 on a fixed surface

DOI10.1016/S0095-8956(02)00027-8zbMath1020.05030MaRDI QIDQ1403910

Carsten Thomassen

Publication date: 20 August 2003

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

zbMATH Keywords

polynomial time4-color-critical graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (29)

Three-coloring Klein bottle graphs of girth five ⋮ Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle. ⋮ Every triangle-free induced subgraph of the triangular lattice is \((5m,2m)\)-choosable ⋮ Hyperbolic families and coloring graphs on surfaces ⋮ Do triangle-free planar graphs have exponentially many 3-colorings? ⋮ Many 3-colorings of triangle-free planar graphs ⋮ 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 ⋮ 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 ⋮ A short list color proof of Grötzsch's theorem ⋮ Fine Structure of 4-Critical Triangle-Free Graphs III. General Surfaces ⋮ Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five ⋮ 3-choosability of planar graphs with \((\leqslant 4)\)-cycles far apart ⋮ From the plane to higher surfaces ⋮ $(3a:a)$-List-Colorability of Embedded Graphs of Girth at Least Five ⋮ 3-list-coloring graphs of girth at least five on surfaces ⋮ Coloring Triangle-Free Graphs on Surfaces ⋮ Coloring near-quadrangulations of the cylinder and the torus ⋮ Coloring even-faced graphs in the torus and the Klein bottle ⋮ Locally planar graphs are 5-choosable ⋮ Online coloring graphs with high girth and high odd girth ⋮ What is on his mind? ⋮ Irreducible 4-critical triangle-free toroidal graphs ⋮ 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 ⋮ Coloring-flow duality of embedded graphs ⋮ Fractional Coloring Methods with Applications to Degenerate Graphs and Graphs on Surfaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generating locally-cyclic triangulations of surfaces
• Coloring graphs without short non-bounding cycles
• Every planar graph is 5-choosable
• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• Color-critical graphs on a fixed surface
• 3-list-coloring planar graphs of girth 5
• Coloring graphs with fixed genus and girth

This page was built for publication: The chromatic number of a graph of girth 5 on a fixed surface