List multicoloring problems involving the k ‐fold Hall numbers

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 ⌈5 k /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 ) ( C 4 )=2 k −⌊ k /3⌋. For longer cycles it is known that h ( k ) ( C n )=2 k , for n odd, and 2 k −⌊ k /( n −1)⌋≤ h ( k ) ( C n )≤2 k , for n even. Here we show the lower bound for n even, and conjecture that this is the right value (just as for C 4 ). We prove that if G is the diamond (a four‐cycle with a diagonal), then h ( k ) ( G )=2 k . 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.