List Multicoloring Problems Involving the k-Fold Hall Numbers

作者：Cropper Mathew^*; Hilton Anthony J W; Johnson Peter D Jr; Lehel Jeno

来源：Journal of Graph Theory, 2010, 65(1): 16-34.

DOI：10.1002/jgt.20462

• list multicoloring
• Hall's conditions
• the k-fold Hall number of graph

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/31; 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))= 2k Lk/3j. For longer cycles it is known that h(C)=2k, for n odd, and 2k Lk/ (n 1) _I < h(k)(C,)< 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 fourcycle with a diagonal), then h(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.

• 出版日期2010-9