List multicoloring problems involving the k-fold Hall numbers
✍ Scribed by Mathew Cropper; Anthony J. W. Hilton; Peter D. Johnson Jr.; Jenö Lehel
- Publisher
- John Wiley and Sons
- Year
- 2009
- Tongue
- English
- Weight
- 159 KB
- Volume
- 65
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
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.