List colourings of graphs (Q2741180)

A list colouring of a graph is a colouring in which each vertex \(v\) receives a colour from a prescribed list \(L(v)\). The list-chromatic number or choosability \(\text{ch}(G)\) is the smallest \(k\) such that a graph always has a proper list colouring provided the prescribed lists are of size at least \(k\). If the lists are the same for each vertex, then \(\text{ch}(G)\) reduces to the usual chromatic number \(\chi(G)\). NEWLINENEWLINENEWLINEThis paper provides an excellent survey of list colourings. A section is devoted to results and conjectures regarding when \(\text{ch}(G) = \chi (G)\). Some time is spent on \((a:b)\)-choosability: each vertex gets a list of \(a\) colours, and we must choose \(b\) of these colours so that adjacent vertices receive disjoint sets. The author also examines \(d\)-defective colourings, where the subgraph induced by vertices receiving a fixed colour has maximum degree \(d\). List versions of Hadwidger's conjecture are given, except in this context one excludes \(K_{r,s}\) minors instead of \(K_r\) minors. Some new results are given regarding defective choosability of planar graphs. Another variation adds the restriction that adjacent vertices have a bound on the number of elements in common in their lists. The paper concludes with a review of different methods of proof for choosability results and examines the strengths and weaknesses of each. NEWLINENEWLINENEWLINEThe paper is excellently written. It is clearly organized and offers a variety of conjectures and open problems. This is a ``must read'' for anyone interested in colouring graphs.NEWLINENEWLINEFor the entire collection see [Zbl 0964.00035].