Hall's condition for list-coloring, and the Hall parameters: Recent developments
type: Item
instance of: scholarly article
title: Hall's condition for list-coloring, and the Hall parameters: Recent developments
zbMATH Open document ID: 1008.05054
DOI: 10.1016/S0012-365X(01)00241-2
published in: Discrete Mathematics
publication date: 2002-05-28T00:00:00Z
review text: 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.
reviewed by: Martin Škoviera
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1746283
zbMATH Keywords: list coloring
zbMATH Keywords: marriage condition
zbMATH Keywords: system of representatives
zbMATH Keywords: Hall number
zbMATH Keywords: list assignment
zbMATH Keywords: critical graphs
zbMATH Keywords: multicolourings
author: P. D. jun. Johnson
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00241-2
OpenAlex ID: W2056817888
Wikidata QID: Q126857471
Recommended article: Q4393389
Recommended article: Extremal jumps of the Hall number
Recommended article: Q3356317
Recommended article: Restricted list coloring and Hall's condition
Recommended article: Q4387751
Recommended article: Q5377013
Recommended article: Hall number for list colorings of graphs: Extremal results
Recommended article: Q4305534
Recommended article: Hall parameters of complete and complete bipartite graphs
Recommended article: Extending the disjoint-representatives theorems of Hall, Halmos, and Vaughan to list-multicolorings of graphs
description: scientific article; zbMATH DE number 1746283