{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,3]],"date-time":"2023-11-03T00:10:58Z","timestamp":1698970258540},"reference-count":18,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2009,12,6]],"date-time":"2009-12-06T00:00:00Z","timestamp":1260057600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2010,9]]},"abstract":"Abstract<\/jats:title>We show that the four\u2010cycle has a k<\/jats:italic>\u2010fold 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 \u23085k<\/jats:italic>\/3\u2309; furthermore, the same is not true with shorter list lengths. In terms of h<\/jats:italic>(k<\/jats:italic>)<\/jats:sup>(G<\/jats:italic>), the k<\/jats:italic> \u2010fold Hall number of a graph G<\/jats:italic>, this result is stated as h<\/jats:italic>(k<\/jats:italic>)<\/jats:sup>(C<\/jats:italic>4<\/jats:sub>)=2k<\/jats:italic>\u2212\u230ak<\/jats:italic>\/3\u230b. For longer cycles it is known that h<\/jats:italic>(k<\/jats:italic>)<\/jats:sup>(C<\/jats:italic>n<\/jats:italic><\/jats:sub>)=2k<\/jats:italic>, for n<\/jats:italic> odd, and 2k<\/jats:italic>\u2212\u230ak<\/jats:italic>\/(n<\/jats:italic>\u22121)\u230b\u2264h<\/jats:italic>(k<\/jats:italic>)<\/jats:sup>(C<\/jats:italic>n<\/jats:italic><\/jats:sub>)\u22642k<\/jats:italic>, for n<\/jats:italic> even. Here we show the lower bound for n<\/jats:italic> even, and conjecture that this is the right value (just as for C<\/jats:italic>4<\/jats:sub>). We prove that if G<\/jats:italic> is the diamond (a four\u2010cycle with a diagonal), then h<\/jats:italic>(k<\/jats:italic>)<\/jats:sup>(G<\/jats:italic>)=2k<\/jats:italic>. Combining these results with those published earlier we obtain a characterization of graphs G<\/jats:italic> with h<\/jats:italic>(k<\/jats:italic>)<\/jats:sup>(G<\/jats:italic>)=k<\/jats:italic>. As a tool in the proofs we obtain and apply an elementary generalization of the classical Hall\u2013Rado\u2013Halmos\u2013Vaughan theorem on pairwise disjoint subset representatives with prescribed cardinalities. \u00a9 2009 Wiley Periodicals, Inc. J Graph Theory 65: 16\u201334, 2010.<\/jats:p>","DOI":"10.1002\/jgt.20462","type":"journal-article","created":{"date-parts":[[2009,12,8]],"date-time":"2009-12-08T00:15:33Z","timestamp":1260231333000},"page":"16-34","source":"Crossref","is-referenced-by-count":0,"title":["List multicoloring problems involving the k<\/i>\u2010fold Hall numbers"],"prefix":"10.1002","volume":"65","author":[{"given":"Mathew","family":"Cropper","sequence":"first","affiliation":[]},{"given":"Anthony J. W.","family":"Hilton","sequence":"additional","affiliation":[]},{"suffix":"Jr.","given":"Peter D.","family":"Johnson","sequence":"additional","affiliation":[]},{"given":"Jen\u00f6","family":"Lehel","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2010,7,21]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(200004)33:4<199::AID-JGT2>3.0.CO;2-7"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10093"},{"key":"e_1_2_1_4_2","first-page":"135","article-title":"List k\u2010fold coloring cycles with Hall's condition","volume":"5","author":"Cropper M.","year":"2008","journal-title":"AKCE Internat J Combin Graph Theory"},{"key":"e_1_2_1_5_2","first-page":"83","article-title":"List multicoloring trees with Hall's condition","volume":"147","author":"Cropper M.","year":"2001","journal-title":"Congr Numer"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00117-0"},{"key":"e_1_2_1_7_2","first-page":"125","article-title":"Choosability in graphs","volume":"26","author":"Erd\u0151s P.","year":"1980","journal-title":"Congr Numer"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10154"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-10.37.26"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.2307\/2372148"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-46908-4_41"},{"key":"e_1_2_1_12_2","first-page":"195","article-title":"Hall's condition for multicoloring","volume":"128","author":"Hilton A. J. W.","year":"1997","journal-title":"Congr Numer"},{"key":"e_1_2_1_13_2","first-page":"161","article-title":"The Hall number of a simple graph","volume":"121","author":"Hilton A. J. W.","year":"1996","journal-title":"Congr Numer"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1155\/2007\/72168"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-44.1.61"},{"key":"e_1_2_1_16_2","volume-title":"Fractional Graph Theory","author":"Scheinerman E. R.","year":"1997"},{"key":"e_1_2_1_17_2","unstructured":"T.Slivnik Extremal problems for cliques and colorings Ph.D. Thesis Cambridge University England 1996."},{"issue":"29","key":"e_1_2_1_18_2","first-page":"3","article-title":"Coloring the vertices of a graph in prescribed colors","volume":"101","author":"Vizing V. G.","year":"1976","journal-title":"Metody Diskret Analiz"},{"key":"e_1_2_1_19_2","volume-title":"Introduction to Graph Theory","author":"West D. B.","year":"2001"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.20462","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.20462","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,2]],"date-time":"2023-11-02T10:48:24Z","timestamp":1698922104000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.20462"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,21]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.1002\/jgt.20462"],"URL":"https:\/\/doi.org\/10.1002\/jgt.20462","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,7,21]]}}}