Extending the disjoint-representatives theorems of Hall, Halmos, and Vaughan to list-multicolorings of graphs
✍ Scribed by Cropper, M. M.; Goldwasser, J. L.; Hilton, A. J. W.; Hoffman, D. G.; Johnson, P. D.
- Publisher
- John Wiley and Sons
- Year
- 2000
- Tongue
- English
- Weight
- 333 KB
- Volume
- 33
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Philip Hall's famous theorem on systems of distinct representatives and its not-so-famous improvement by Halmos and Vaughan (1950) can be regarded as statements about the existence of proper list-colorings or listmulticolorings of complete graphs. The necessary and sufficient condition for a proper "coloring" in these theorems has a rather natural generalization to a condition we call Hall's condition on a simple graph G, a vertex list assignment to G, and an assignment of nonnegative integers to the vertices of G. Hall's condition turns out to be necessary for the existence of a proper multicoloring of G under these assignments. The Hall-Halmos-Vaughan theorem may be stated: when G is a clique, Hall's condition is sufficient for the existence of a proper multicoloring.
In this article, we undertake the study of the class HHV of simple graphs G for which Hall's condition is sufficient for the existence of a proper multicoloring. It is shown that HHV is contained in the class H 0 of graphs in which every block is a clique and each cut-vertex lies in exactly two blocks. On the other hand, besides cliques, the only connected graphs we know to be in HHV are (i) any two cliques joined at a cut-vertex, (ii) paths, and (iii) the two connected graphs of order 5 in H 0 , which are neither cliques, paths, nor two cliques stuck together. In case (ii), we address the constructive aspect, the problem of deciding if there is a proper coloring and, if there is, of finding one.