Three-coloring Klein bottle graphs of girth five

DOI10.1016/j.jctb.2004.05.001zbMath1052.05027OpenAlexW1986461743MaRDI QIDQ1880794

Barrett Walls, Robin Thomas

Publication date: 1 October 2004

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

Full work available at URL: https://doi.org/10.1016/j.jctb.2004.05.001

zbMATH Keywords

torusprojective planeKlein bottleimbeddable3-colorable

Mathematics Subject Classification ID

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

Related Items (max. 100)

Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle. ⋮ 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 ⋮ On the minimum number of edges in triangle-free 5-critical graphs ⋮ Characterization of 4-critical triangle-free toroidal graphs ⋮ Structure in sparse \(k\)-critical graphs ⋮ Fine Structure of 4-Critical Triangle-Free Graphs II. Planar Triangle-Free Graphs with Two Precolored 4-Cycles ⋮ A density bound for triangle‐free 4‐critical graphs ⋮ Fine Structure of 4-Critical Triangle-Free Graphs III. General Surfaces ⋮ Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five ⋮ Short proofs of coloring theorems on planar graphs ⋮ Coloring near-quadrangulations of the cylinder and the torus ⋮ Coloring even-faced graphs in the torus and the Klein bottle ⋮ 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. V: Coloring planar graphs with distant anomalies ⋮ Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs ⋮ Planar 4-critical graphs with four triangles ⋮ Decomposing a planar graph of girth 5 into an independent set and a forest

Cites Work

• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• Color-critical graphs on a fixed surface
• The chromatic number of a graph of girth 5 on a fixed surface
• A 4-color theorem of the Klein bottle
• Coloring graphs with fixed genus and girth
• 4-chromatic projective graphs
• A 4-Color Theorem for Toroidal Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Three-coloring Klein bottle graphs of girth five