Five-coloring graphs on the Klein bottle

2012/01/25 by Nathan Chenette, Chenette, Nathan, Luke Postle +7
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems #math.CO

paper · pdf · doi:10.48550/arxiv.1201.5361

40 pages, 7 figures

arxiv created 2012/01/25 · openalex publication_date 2012/01/25 · arxiv updated 2012/01/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface

Related

• Graphs without a 3-connected subgraph are 4-colorable
• Coloring graphs with crossings
• k-Colorability of P5-free graphs
• Odd list-coloring of graphs of small Euler genus with no short cycles of specific types
• Deciding k-colourability of P₅-free graphs in polynomial time