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. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1016/j.endm.2008.06.047 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Klein bottle,6-critical,5-colorable,subgraph | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Klein bottle,Eulerian path,Isomorphism,Triangulation (social science),If and only if,Mathematics | Journal |
Volume | ISSN | Citations |
31 | 1571-0653 | 0 |
PageRank | References | Authors |
0.34 | 6 | 9 |
Name | Order | Citations | PageRank |
---|---|---|---|
Nathan Chenette | 1 | 531 | 17.37 |
Luke Postle | 2 | 40 | 15.29 |
Noah Streib | 3 | 24 | 4.81 |
Robin Thomas | 4 | 89 | 11.20 |
Carl Yerger | 5 | 3 | 1.12 |
Ken-ichi Kawarabayashi | 6 | 1731 | 149.16 |
Daniel Král' | 7 | 426 | 46.78 |
jan kyncl | 8 | 97 | 18.56 |
Bernard Lidický | 9 | 181 | 23.68 |