Five-list-coloring graphs on surfaces I. Two lists of size two in planar graphs

Luke Postle, Robin Thomas

Published 2014-02-08, updated 2014-08-05Version 2

Let G be a plane graph with outer cycle C, let u,v be vertices of C and let (L(x):x in V(G)) be a family of sets such that |L(u)|=|L(v)|=2, L(x) has at least three elements for every vertex x of C-{u,v} and L(x) has at least five elements for every vertex x of G-V(C). We prove a conjecture of Hutchinson that G has a (proper) coloring f such that f(x) belongs to L(x) for every vertex x of G. We will use this as a lemma in subsequent papers.