List multicoloring problems involving the k‐fold Hall numbers |
| |
Authors: | Mathew Cropper Anthony J W Hilton Peter D Johnson Jr Jenö Lehel |
| |
Institution: | 1. Department of Mathematics and Statistics, Eastern Kentucky University, Richmond, KY 40475‐3133;2. School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS United Kingdom;3. Department of Mathematics, The University of Reading, Reading RG6, 6AX, England, United Kingdom;4. Department of Mathematics and Statistics, Auburn University, Auburn, AL 36849‐5310;5. Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152‐3240;6. Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, Hungary |
| |
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 ?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. |
| |
Keywords: | list multicoloring Hall's conditions the k‐fold Hall number of graph |
|
|