Coloring even-faced graphs in the torus and the Klein bottle

KRÁĽ, Daniel a R THOMAS. Coloring even-faced graphs in the torus and the Klein bottle. Combinatorica : an international journal of the János Bolyai Mathematical Society. Budapest: Mathematical Institute of the Hungarian Academy of Sciences, 2008, roč. 28, č. 3, s. 325-341. ISSN 0209-9683. Dostupné z: https://doi.org/10.1007/s00493-008-2315-z.

Základní údaje

Originální název

Coloring even-faced graphs in the torus and the Klein bottle

Autoři

KRÁĽ, Daniel a R THOMAS

Vydání

Combinatorica : an international journal of the János Bolyai Mathematical Society, Budapest, Mathematical Institute of the Hungarian Academy of Sciences, 2008, 0209-9683

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.790

Označené pro přenos do RIV

Ne

DOI

https://doi.org/10.1007/s00493-008-2315-z

UT WoS

000258004800005

---

Anotace

V originále

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.