List multicoloring problems involving the k-fold Hall numbers
Mathew Cropper, Anthony J. W. Hilton, Peter D. Johnson, Jenő Lehel · SZTAKI Publication Repository (Hungarian Academy of Sciences) · 2010
We show that the four-cycle has a k-fold list coloring if the lists of colors available at the vertices satisfy the necessary Hall's condition, and if each list has length at least ⌈5k-3⌉; furthermore, the same is not true with shorter list lengths. In terms of h(k)(G), the k -fold Hall number of a graph G, this result is stated as h(k)(C4)=2k-⌊k-3⌋. For longer cycles it is known that h(k)(Cn)=2k, for n odd, and 2k-⌊k-(n-1)⌋≤h(k)(Cn)≤2k, for n even. Here we show the lower bound for n even, and conjecture that this is the right value (just as for C4). We prove that if G is the diamond (a four-cycle with a diagonal), then h(k)(G)=2k. Combining these results with those published earlier we obtain a characterization of graphs G with h(k)(G)=k. As a tool in the proofs we obtain and apply an elementary generalization of the classical Hall–Rado–Halmos–Vaughan theorem on pairwise disjoint subset representatives with prescribed cardinalities. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 16–34, 2010.