Asymptotically the List Colouring Constants Are 1

✍ Scribed by Bruce Reed; Benny Sudakov

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 129 KB
• Volume: 86
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.2002.2110

✦ Synopsis

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 jSðvÞj ¼ ð1 þ oð1ÞÞd and for each colour c 2 SðvÞ; 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.