Five-coloring graphs on the Klein bottle

DOI10.1016/J.JCTB.2012.05.001MaRDI QIDQ713974zbMATH OpenOpenAlexFDO

Authors Nathan Chenette, Luke Postle, Noah Streib, Robin Thomas, Carl Yerger

Publication date 19 October 2012

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

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

zbMATH Keywords

graph coloringKlein bottle

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: We exhibit an explicit list of nine graphs such that a graph drawn in the Klein bottle is 5-colorable if and only if it has no subgraph isomorphic to a member of the list.

Recommendations

• Six-Critical Graphs on the Klein Bottle
• Three-coloring Klein bottle graphs of girth five
• Coloring even-faced graphs in the torus and the Klein bottle
• A 4-color theorem of the Klein bottle
• Coloring Eulerian triangulations of the Klein bottle

Cites work

• scientific article; zbMATH DE number 5823677 (Why is no real title available?)
• scientific article; zbMATH DE number 3769646 (Why is no real title available?)
• scientific article; zbMATH DE number 49719 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3450230 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• 6-Critical Graphs on the Klein Bottle
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Color-critical graphs on a fixed surface
• Every Planar Map is Four Colorable
• Every planar graph is 5-choosable
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Five-coloring graphs on the torus
• Graphs on surfaces
• Map-Colour Theorems
• On critical subgraphs of colour-critical graphs
• Some remarks on Hajós' conjecture
• Subgraph Isomorphism in Planar Graphs and Related Problems
• The Colouring of Maps
• The four-colour theorem
• The non-existence of colorings
• Triangulations and the Hajós conjecture
• Triangulations and the Hajós conjecture

Cited in

(11)

• Hyperbolic families and coloring graphs on surfaces
• Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle.
• 5-list coloring toroidal 6-regular triangulations in linear time
• A (5,5)-Colouring of K_n with Few Colours
• The optimal drawings of \(K_{5,n}\)
• Five-coloring graphs on the torus
• Some Conjectures and Questions in Chromatic Topological Graph Theory
• Three-coloring Klein bottle graphs of girth five
• On graphical quintuple systems
• Six-Critical Graphs on the Klein Bottle
• A 4-color theorem of the Klein bottle

This page was built for publication: Five-coloring graphs on the Klein bottle

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