Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle

DVORAK, Z; Daniel KRÁĽ a R THOMAS. Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle. JOURNAL OF COMBINATORIAL THEORY SERIES B. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE, 2016, roč. 120, s. 1-17. ISSN 0095-8956. Dostupné z: https://doi.org/10.1016/j.jctb.2016.04.003.

Základní údaje

Originální název

Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle

Autoři

DVORAK, Z; Daniel KRÁĽ a R THOMAS

Vydání

JOURNAL OF COMBINATORIAL THEORY SERIES B, SAN DIEGO, ACADEMIC PRESS INC ELSEVIER SCIENCE, 2016, 0095-8956

---

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.829

Označené pro přenos do RIV

Ne

DOI

https://doi.org/10.1016/j.jctb.2016.04.003

UT WoS

000377833100001

Klíčová slova anglicky

Graph coloring; Planar graphs; Precoloring extension

---

Anotace

V originále

Let G be a plane graph with exactly one triangle T and all other cycles of length at least 5, and let C be a facial cycle of G of length at most six. We prove that a 3-coloring of C does not extend to a 3-coloring of G if and only if C has length exactly six and there is a color x such that either G has an edge joining two vertices of C colored x, or T is disjoint from C and every vertex of T is adjacent to a vertex of C colored x. This is a lemma to be used in a future paper of this series. (C) 2016 Elsevier Inc. All rights reserved.