Informace o publikaci
Coloring even-faced graphs in the torus and the Klein bottle
| Autoři | |
|---|---|
| Rok publikování | 2008 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Combinatorica : an international journal of the János Bolyai Mathematical Society |
| Citace | |
| Doi | http://dx.doi.org/10.1007/s00493-008-2315-z |
| Popis | We prove that a triangle-free graph drawn in the torus with all faces bounded by even walks is 3-colorable if and only if it has no subgraph isomorphic to the Cayley graph C (Z(13); 1, 5). We also prove that a non-bipartite quadrangulation of the Klein bottle is 3-colorable if and only if it has no non-contractible separating cycle of length at most four and no odd walk homotopic to a non-contractible two-sided simple closed curve. These results settle a conjecture of Thomassen and two conjectures of Archdeacon, Hutchinson, Nakamoto, Negami and Ota. |