Article ID Journal Published Year Pages File Type
4656771 Journal of Combinatorial Theory, Series B 2015 8 Pages PDF
Abstract

Let G be a plane graph with outer cycle C  , let v1,v2∈V(C)v1,v2∈V(C) and let (L(v):v∈V(G))(L(v):v∈V(G)) be a family of sets such that |L(v1)|=|L(v2)|=2|L(v1)|=|L(v2)|=2, |L(v)|≥3|L(v)|≥3 for every v∈V(C)∖{v1,v2}v∈V(C)∖{v1,v2} and |L(v)|≥5|L(v)|≥5 for every v∈V(G)∖V(C)v∈V(G)∖V(C). We prove a conjecture of Hutchinson that G has a (proper) coloring ϕ   such that ϕ(v)∈L(v)ϕ(v)∈L(v) for every v∈V(G)v∈V(G). We will use this as a lemma in subsequent papers.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,