zbMATH — the first resource for mathematics

Extending the disjoint-representatives theorems of Hall, Halmos, and Vaughan to list-multicolorings of graphs. (English) Zbl 0944.05040
Philip Hall’s theorem on systems of distinct representatives [J. Lond. Math. Soc. 10, 26-30 (1935; Zbl 0010.34503)] and an improvement by P. R. Halmos and H. E. Vaughan [Am. J. Math. 72, 214-215 (1950; Zbl 0034.29601)] can be interpreted as statements about the existence of proper list-colorings or list-multicolorings of complete graphs. The Hall-Halmos-Vaughan theorem can be stated: if \(G\) is a clique, then Hall’s condition is sufficient for the existence of a proper multicoloring. The present authors study the class HHV of simple graphs \(G\) for which Hall’s condition guarantees the existence of a proper multicoloring. They also show that HHV is contained in the class of graphs for which every block is a clique and each cut-vertex is in exactly two blocks. For paths, the authors address the problem of deciding if this is a proper coloring and, if so, of finding one.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Hall, J London Math Soc 10 pp 26– (1935) · Zbl 0010.34503 · doi:10.1112/jlms/s1-10.37.26
[2] Halmos, Am J Math 72 pp 214– (1950) · Zbl 0034.29601 · doi:10.2307/2372148
[3] and ?A variation of Ryser’s theorem and a necessary condition for the list-colouring problem,? Graph colourings, and (Editors), Pitman Research Notes in Mathematics Series 218, Longman Scientific and Technical, Wiley, Harlow, Essex, and New York, 1990, pp. 135-143.
[4] and Extending Hall’s theorem, Topics in combinatorics and graph theory; Essays in honour of Gerhard Ringel, Physica-Verlag, Heidelberg, pp. 360-371.
[5] Hilton, Congress Numer 121 pp 161– (1996)
[6] Hilton, Congress Numer 128 pp 195– (1997)
[7] Introduction to graph theory, Prentice Hall Upper Saddle River, NJ, 1996. · Zbl 0891.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.