Hall's condition for list-coloring, and the Hall parameters: Recent developments
In a list colouring of a graph \(G\), each vertex \(v\) of \(G\) is assigned a list \(L(v)\) of ``permitted'' colours and it is required to find a colouring \(\phi\) of \(G\) such that for each vertex \(v\) one has \(\phi(v)\in L(v)\), and that adjacent vertices are assigned distinct colours. The list colouring number \(c(G)\) of \(G\) is the smallest integer \(m\) such that \(G\) can be list-coloured with respect to any list assignment where \(|L(v)|\geq m\) for each vertex \(v\). In 1988 \textit{A. J. W. Hilton} [J. Comb. Math. Comb. Comput. 3, 121-134 (1988; Zbl 0661.05025)] realized that list-colouring problems are strongly related to the area of systems of distinct representatives. A proper list-colouring can be thought of as a system of representatives of the system \((L(v))_v\) where the representatives are only required to be distinct when the corresponding vertices are adjacent. Moreover, \textit{A. J. W. Hilton} and \textit{P. D. Johnson} [Topics in combinatorics and graph theory. Essays in honour of Gerhard Ringel, 360-371 (1990; Zbl 0731.05017)] observed that Hall's marriage condition can be generalized in a natural way to graphs with list assignments. With this generalization, one can define the Hall number \(h(G)\) of a graph \(G\) to be the smallest positive integer among those \(m\) for which there exists an \(L\)-colouring of \(G\) whenever \(G\) and the list assignment \(L\) satisfy Hall's condition, and \(|L(v)|\geq m\). The paper surveys recent development of these ideas, covering such topics as critical graphs with respect to the Hall number, list-colourings with a restricted number of colours, multicolourings, and others.
scientific article; zbMATH DE number 1746283