Hall's condition for list-coloring, and the Hall parameters: Recent developments (Q1598850)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hall's condition for list-coloring, and the Hall parameters: Recent developments |
scientific article |
Statements
Hall's condition for list-coloring, and the Hall parameters: Recent developments (English)
0 references
28 May 2002
0 references
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.
0 references
list coloring
0 references
marriage condition
0 references
system of representatives
0 references
Hall number
0 references
list assignment
0 references
critical graphs
0 references
multicolourings
0 references