Five-list-coloring graphs on surfaces III. One list of size one and one list of size two

preprint2016arXivOpen access

Abstract

Let GG be a plane graph with outer cycle CC and let (L(v):v∈V(G))(L(v):v\in V(G)) be a family of non-empty sets. By an LL-coloring of GG we mean a (proper) coloring ϕϕ of GG such that ϕ(v)∈L(v)ϕ(v)\in L(v) for every vertex vv of GG. Thomassen proved that if v1,v2∈V(C)v_1,v_2\in V(C) are adjacent, L(v1)≠L(v2)L(v_1)\ne L(v_2), ∣L(v)∣≥3|L(v)|\ge3 for every v∈V(C)−{v1,v2}v\in V(C)-\{v_1,v_2\} and ∣L(v)∣≥5|L(v)|\ge5 for every v∈V(G)−V(C)v\in V(G)-V(C), then GG has an LL-coloring. What happens when v1v_1 and v2v_2 are not adjacent? Then an LL-coloring need not exist, but in the first paper of this series we have shown that it exists if ∣L(v1)∣,∣L(v2)∣≥2|L(v_1)|,|L(v_2)|\ge2. Here we characterize when an LL-coloring exists if ∣L(v1)∣≥1|L(v_1)|\ge1 and ∣L(v2)∣≥2|L(v_2)|\ge2. This result is a lemma toward a more general theorem along the same lines, which we will use to prove that minimally non-LL-colorable planar graphs with two precolored cycles of bounded length are of bounded size. The latter result has a number of applications which we pursue elsewhere.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.