Informace o publikaci
Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle
| Autoři | |
|---|---|
| Rok publikování | 2016 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | JOURNAL OF COMBINATORIAL THEORY SERIES B |
| Citace | |
| Doi | http://dx.doi.org/10.1016/j.jctb.2016.04.003 |
| Klíčová slova | Graph coloring; Planar graphs; Precoloring extension |
| Popis | 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. |