A Note on Vertex List Colouring

Source abstract

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 ] = 2 k 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.