Atlas home || Conferences | Abstracts | about Atlas

21st Cumberland Conference on Graph Theory, Combinatorics, and Computing ---In Honor of Mike Plummer's 70th Birthday
May 15-17, 2008
Vanderbilt University
Nashville, TN, USA

Organizers
Mark Ellingham and Gexin Yu

View Abstracts
Conference Homepage

Five-coloring graphs on the Klein bottle
by
Luke Postle
Georgia Institute of Technology
Coauthors: Nathan Chenette, Noah Streib, Robin Thomas, Carl Yerger

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 Kral, Mohar, Nakamoto, Pangrac 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.

Date received: April 12, 2008

Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cawn-32.