A Note on Vertex List Colouring
Penny E. Haxell · Combinatorics Probability Computing · 2001
Let k be a positive integer and let G be a graph. Suppose a list S(v) of positive integers is assigned to each vertex v, such that (1) [mid ]S(v)[mid ] = 2k for each vertex v of G, and (2) for each vertex v, and each c ∈ S(v), the number of neighbours w of v for which c ∈ S(w) is at most k. Then we prove that there exists a proper vertex colouring f of G such that f(v) ∈ S(v) for each v ∈ V(G). This proves a weak version of a conjecture of Reed.