In this paper we prove the following result about vertex list colourings, which shows that a conjecture of the first author (1999, J. Graph Theory 31, 149-153) is asymptotically correct. Let G be a graph with the sets of lists S(v), satisfying that for every vertex S(nu) = (1 + o(1))d and for each colour c is an element of S(nu), the number of neighbours of v that have c in their list is at most d. Then there exists a proper colouring of G from these lists. (C) 2002 Elsevier Science (USA) [References: 11]
展开▼
