Six-Critical Graphs on the Klein bottle Extended Abstract
Nathan Chenette, Ken‐ichi Kawarabayashi, Daniel Kr, Luke Postle, Noah Streib, Robin B. Thomas, Carl Yerger · 2007
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. This answers a question of Thomassen [J. Comb. Theory Ser. B 70 (1997), 67{100] and implies an earlier result of Kr al’, Mohar, Nakamoto, Pangr ac and Suzuki that an Eulerian triangulation of the Klein bottle is 5-colorable if and only if it has no complete subgraph on six vertices.