Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656671 | Journal of Combinatorial Theory, Series B | 2016 | 17 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Zdeněk Dvořák, Daniel Král', Robin Thomas,