Extending the disjoint-representatives theorems of Hall, Halmos, and Vaughan to list-multicolorings of graphs

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 list-multicolori ngs of complete graphs. The necessary and sufficient condition for a proper "coloring" in these theorems has a rather natural generalization to a cond ition we call Hall's condition on a simple graph G, a vertex list assignmen t to G, and an assignment of nonnegative integers to the vertices of G. Hal l's condition turns out to be necessary for the existence of a proper multi coloring 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 exist ence 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 f or the existence of a proper multicoloring. It is shown that HHV is contain ed 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. (C) 2000 John Wiley & Sons, Inc.