{"entities":{"Q2411512":{"pageid":2422255,"ns":120,"title":"Item:Q2411512","lastrevid":52939922,"modified":"2026-01-23T20:50:52Z","type":"item","id":"Q2411512","labels":{"en":{"language":"en","value":"Strengthening \\((a,b)\\)-choosability results to \\((a,b)\\)-paintability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6797312"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411512$3A5F05CF-04FA-4CFA-B186-7622C6138AB4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2d201b396a4afd382070f3f4c5b96f08f2cb2477","datavalue":{"value":{"text":"Strengthening \\((a,b)\\)-choosability results to \\((a,b)\\)-paintability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2411512$726C248E-871F-49E1-BAED-37A3AAFAAEBA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"adcd1bcba2774d70127f25c8a09ee9f3a0c0f3db","datavalue":{"value":"1372.05079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2411512$E1D5F982-69F1-4031-8AC9-88F42F43EA95","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c0f3836db0bbf4c9d19a464cb1573ded99ce3783","datavalue":{"value":{"entity-type":"item","numeric-id":497321,"id":"Q497321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411512$AE2DA51F-9501-4FE6-A0F4-0F04715FB1D1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411512$2FA79829-F909-49D8-89D6-93EC932D77A5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c5a04010440d7ffd7654f08953b21d31e131a50b","datavalue":{"value":{"time":"+2017-10-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2411512$45FF610A-AFB8-463D-A3D2-DC80836CB04C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4273f91cd5172d58e586b8d3e520a43c0e875acb","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i4p26","type":"string"},"datatype":"url"},"type":"statement","id":"Q2411512$5298BC90-B714-44DF-9A76-3D3B1FE9212A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"515aed7c3b0db9ba0cba73bb31111922ae340f21","datavalue":{"value":"Summary: Let \\(a,b\\in\\mathbb{N}\\). A graph \\(G\\) is \\((a,b)\\)-choosable if for any list assignment \\(L\\) such that \\(|L(v)|\\geq a\\), there exists a coloring in which each vertex \\(v\\) receives a set \\(C(v)\\) of \\(b\\) colors such that \\(C(v)\\subseteq L(v)\\) and \\(C(u)\\cap C(w)=\\emptyset\\) for any \\(uw\\in E(G)\\). In the online version of this problem, on each round, a set of vertices allowed to receive a particular color is marked, and the coloring algorithm chooses an independent subset of these vertices to receive that color. We say \\(G\\) is \\((a,b)\\)-paintable if when each vertex \\(v\\) is allowed to be marked \\(a\\) times, there is an algorithm to produce a coloring in which each vertex \\(v\\) receives \\(b\\) colors such that adjacent vertices receive disjoint sets of colors.  We show that every odd cycle \\(C_{2k+1}\\) is \\((a,b)\\)-paintable exactly when it is \\((a,b)\\)-chosable, which is when \\(a\\geq2b+\\lceil b/k\\rceil\\). \\textit{X. Zhu} [Electron. J. Comb. 16, No. 1, Research Paper R127, 16 p. (2009; Zbl 1186.05061)] conjectured that if \\(G\\) is \\((a,1)\\)-paintable, then \\(G\\) is \\((am,m)\\)-paintable for any \\(m\\in\\mathbb{N}\\). The following results make partial progress towards this conjecture. Strengthening results of \\textit{Z. Tuza} and \\textit{M. Voigt} [J. Graph Theory 22, No. 3, 245--252 (1996; Zbl 0853.05034)], and of \\textit{U. Schauz} [Electron. J. Comb. 16, No. 1, Research Paper R77, 18 p. (2009; Zbl 1186.05085)], we prove for any \\(m \\in \\mathbb{N}\\) that \\(G\\) is \\((5m,m)\\)-paintable when \\(G\\) is planar. Strengthening work of Tuza and Voigt [loc. cit.], and of \\textit{J. Hladky} et al. [Discrete Math. 310, No. 23, 3426--3428 (2010; Zbl 1222.05061)], we prove that for any connected graph \\(G\\) other than an odd cycle or complete graph and any \\(m\\in\\mathbb{N}\\), \\(G\\) is \\((\\Delta(G)m,m)\\)-paintable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2411512$45B77BDA-BC25-4CA9-AA41-ADD6E2B3F768","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2411512$8667F174-2073-451A-8859-3A6A63C808E0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8bd7b7e6f84c655f17cae3d5bd3d43ab98b6376c","datavalue":{"value":"6797312","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2411512$0FF8224D-BDB8-4723-B952-FCAA7DCC519D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2411512$2105CBCB-F8D7-4731-A322-4472AD2E4385","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61e6e8d01418719e15aa61073bc585c328090187","datavalue":{"value":"paintability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2411512$E9C6ECC8-6BCA-49C0-B183-778605F67491","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4635d8c5c6b58a938c5ed2dfeb1923517940e16b","datavalue":{"value":"online list coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2411512$442CE93A-4A9F-4F56-A221-78664523889B","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411512$36AB0511-DECD-4FB3-BF6A-3631C650D4CF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a92ab907df072bb20a1057061523b1fdda43679","datavalue":{"value":{"entity-type":"item","numeric-id":5782525,"id":"Q5782525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411512$B97F9044-DBE3-439A-9F80-72EE469A2E48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3573b87026595a32002fa2dc54ac8b096bc29f3f","datavalue":{"value":{"entity-type":"item","numeric-id":3922703,"id":"Q3922703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411512$42CB0557-37AA-4810-B27B-730B57BCBC2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f79a257513617dfd1ba9205348dca5c21be0bc1","datavalue":{"value":{"entity-type":"item","numeric-id":712277,"id":"Q712277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411512$AFE643F6-4D36-4198-B7F1-B37229DD63C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"524331c6d7d5f6c9274fa5df89127973717f3672","datavalue":{"value":{"entity-type":"item","numeric-id":2344816,"id":"Q2344816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411512$F7F776CD-A67C-4543-813F-214F6D9D3D40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bcf2b4c2b6c7326a3acf6bf57028e463e8c28e","datavalue":{"value":{"entity-type":"item","numeric-id":2380232,"id":"Q2380232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411512$45E8B106-503F-4269-83CE-397976D97287","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8e9a01d057f2ac8669e7cac2ad5d67b6775d2fa","datavalue":{"value":{"entity-type":"item","numeric-id":1333334,"id":"Q1333334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411512$57D8B0F8-F231-41D9-8E7E-312CFCC8A120","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c53383b20cd8dab8afe9fd49c12dd8033db5f6eb","datavalue":{"value":{"entity-type":"item","numeric-id":4888118,"id":"Q4888118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411512$95FF2D34-1BBB-451E-92C3-3C450F4A3F24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92077b84d7a6aabab7f2ca3e178b3e89c72e8c83","datavalue":{"value":{"entity-type":"item","numeric-id":2380291,"id":"Q2380291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2411512$232463E1-4116-464F-888B-7640BA05E9A6","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"2575451b3c8af6d5cf71052110b9336ac698e162","datavalue":{"value":"bafkreidzwnrmkjx5zosyg6fdh2yzrhtoyjgpswyan7e5cpy25hrfo3mivm","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2411512$029045CE-1688-4330-B3B5-44774CC50B91","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea68b01edcb95d758d21f5b224e23d624a55c8d8","datavalue":{"value":{"entity-type":"item","numeric-id":6056763,"id":"Q6056763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01c998df5b82a6baa39e056cbf9c07bdb3533c4c","datavalue":{"value":{"amount":"+0.8094144463539124","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2411512$1D843E91-ABB5-468E-A13B-686036905D69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9c910fa70da918ca22835bae87a408f4345cdca","datavalue":{"value":{"entity-type":"item","numeric-id":2344816,"id":"Q2344816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"510e8847b691dc6df0b11afa5f5d193aebb38018","datavalue":{"value":{"amount":"+0.8073921203613281","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2411512$3627D625-552D-46C6-A6F3-224BB8C14DAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb64e4153363b9a76c30d1d7932364dcf6a3a0ad","datavalue":{"value":{"entity-type":"item","numeric-id":2448254,"id":"Q2448254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7076a281ca8bb30f9acaba9e24741858a5e7c46","datavalue":{"value":{"amount":"+0.8038903474807739","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2411512$468C5A90-6125-4C94-BAC2-75B43454C91B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00f1985e2c6e7568e7e7efb457469b8bb4546977","datavalue":{"value":{"entity-type":"item","numeric-id":5272926,"id":"Q5272926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffa912c4cd44500eb3523f9aa3f9701bf963774e","datavalue":{"value":{"amount":"+0.7932705283164978","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2411512$6B89CB9C-A28A-4191-B6AC-E91B18060F8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91cd62c6a219dd01af7d21bae71ebd7c0bcd8bb2","datavalue":{"value":{"entity-type":"item","numeric-id":4882474,"id":"Q4882474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b923bfc2fb52940035831dd1330a6dadaf3c71b5","datavalue":{"value":{"amount":"+0.793031632900238","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2411512$2BA1B14C-0CC2-4D96-B16D-1F2D9D6C326E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2411512","badges":[]}}}}}