Six-Critical Graphs on the Klein Bottle |
| |
| Institution: | 1. Department of Mathematics, North Carolina State University, Box 8205, Raleigh, NC 27695, United States;2. Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, United States;3. Department of Mathematics and Computer Science, Davidson College, Davidson, NC 28035, United States;1. Institut für Optimierung und Operations Research, Universität Ulm, Ulm, Germany;2. Institut für Informatik, Universität Rostock, Rostock, Germany |
| |
| 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. This answers a question of Thomassen J. Comb. Theory Ser. B 70 (1997), 67–100] and implies an earlier result of Král', Mohar, Nakamoto, Pangrác 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
