{"entities":{"Q2517653":{"pageid":2528396,"ns":120,"title":"Item:Q2517653","lastrevid":73277226,"modified":"2026-04-14T15:14:58Z","type":"item","id":"Q2517653","labels":{"en":{"language":"en","value":"Completing partial proper colorings using Hall's condition"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6476260"}},"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":"Q2517653$D171FD78-2C57-435E-A981-FB1D23306E76","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"37aed2bd321cf81bf1ab950eb6863fddb9a4ddc4","datavalue":{"value":{"text":"Completing partial proper colorings using Hall's condition","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2517653$D03E43FD-A35B-47B9-93F1-AE49DD4968D0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"50569ffdf19c7dc256b8287a17639e9548ccd3d2","datavalue":{"value":"1325.05080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2517653$C07EFF2D-C83B-4AF6-A411-ECBA03152F29","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8a2ed27fc01e9cc3552366c5d76dc602b91dde9d","datavalue":{"value":{"entity-type":"item","numeric-id":2089532,"id":"Q2089532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517653$6F9E1AB6-C8B3-4A8F-AE3F-21BF771711FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6afd4f89e3b603f11fcdb7aea41b2d200fc501d1","datavalue":{"value":{"entity-type":"item","numeric-id":396807,"id":"Q396807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517653$FA8223FF-0238-4945-9BE6-8D46476422C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"69bf0974b1ee85320267fa13d787edb6babf9e34","datavalue":{"value":{"entity-type":"item","numeric-id":397159,"id":"Q397159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517653$6AA9FAA7-2441-44E6-96C7-9C0AE59628F8","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":"Q2517653$123514E9-3E26-4475-A8A1-C6194F78A912","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f5d7e575ce06abec1e01331d693d8d1b08ceff3b","datavalue":{"value":{"time":"+2015-08-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2517653$74BBFFE6-693E-4960-A195-0CE818E71F6C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e67b405890b231ba79432078c906589655709529","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p6","type":"string"},"datatype":"url"},"type":"statement","id":"Q2517653$0023EBA6-78BB-4093-9D79-2500B615420A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3f7677b07227bedb4ad9e34103a57fdd0df51fb9","datavalue":{"value":"Summary: In the context of list-coloring the vertices of a graph, Hall's condition is a generalization of Hall's Marriage Theorem and is necessary (but not sufficient) for a graph to admit a proper list-coloring. The graph \\(G\\) with list assignment \\(L\\) satisfies \\textit{Hall's condition} if for each subgraph \\(H\\) of \\(G\\), the inequality \\(|V(H)| \\leq \\sum_{\\sigma \\in \\mathcal{C}} \\alpha(H(\\sigma, L))\\) is satisfied, where \\(\\mathcal{C}\\) is the set of colors and \\(\\alpha(H(\\sigma, L))\\) is the independence number of the subgraph of \\(H\\) induced on the set of vertices having color \\(\\sigma\\) in their lists. A list assignment \\(L\\) to a graph \\(G\\) is called \\textit{Hall} if \\((G,L)\\) satisfies Hall's condition. A graph \\(G\\) is \\textit{Hall} \\(m\\)-{completable} for some \\(m \\geq \\chi(G)\\) if every partial proper \\(m\\)-coloring of \\(G\\) whose corresponding list assignment is Hall can be extended to a proper coloring of \\(G\\). In [Australas. J. Comb. 49, 127--151 (2011; Zbl 1228.05083)], \\textit{B. B. Bobga} et al. posed the following questions: (1) Are there examples of graphs that are Hall \\(m\\)-completable, but not Hall \\((m+1)\\)-completable for some \\(m \\geq 3\\)? (2) If \\(G\\) is neither complete nor an odd cycle, is \\(G\\) Hall \\(\\Delta(G)\\)-completable? This paper establishes that for every \\(m \\geq 3\\), there exists a graph that is Hall \\(m\\)-completable but not Hall \\((m+1)\\)-completable and also that every bipartite planar graph \\(G\\) is Hall \\(\\Delta(G)\\)-completable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517653$07ECE877-EA4E-4574-BFC5-B441AE323C01","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2517653$720B8A05-3FEE-460A-88E8-0C43F13DEA5F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d36d25e7872ec43609715792fa7118e5ecc779fc","datavalue":{"value":"6476260","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2517653$0120EB46-1614-4067-A18B-718466CD0897","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5f6aefdf1ffec3bc08d67d0b64a04330c0d9134","datavalue":{"value":"list coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517653$F9A031D4-56A7-4C30-AF98-BB0DA0EBA797","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"118cc985eba23e986e48184ae61fb521488dcd1d","datavalue":{"value":"Hall's condition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517653$91DEE031-3702-4081-A1A6-DCF3E467030D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1854f6cb49e247564b31a5a24bd2ee57583d42a5","datavalue":{"value":"Hall \\(m\\)-completable","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517653$C61AD812-C859-423F-8BF7-DB3348019E9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"247d40d06ae26f8cc2879af875fd9e822dedeb7a","datavalue":{"value":"Hall number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517653$7A85317F-E33C-44E6-A520-8E9698EDC8D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"158eea77b2005ad125e78c69386d91e56f900446","datavalue":{"value":"partial proper coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517653$F0998AA7-1EFA-4DCD-B8EF-CFD19DEE6A8D","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":"Q2517653$861F142D-5356-47F4-8937-D8C16F8F84FA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdd0676f008d3d35603ace258b7c421e863d9a84","datavalue":{"value":{"entity-type":"item","numeric-id":1196681,"id":"Q1196681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517653$DF540139-FCC1-4E39-80A7-0E35494463C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e115ce9c47178ec45694a018c179fa09a828363","datavalue":{"value":{"entity-type":"item","numeric-id":3090471,"id":"Q3090471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517653$9012BA49-D95E-4479-A136-3FF6AB425D88","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":"Q2517653$19A54C80-56CB-41D1-9F66-A1B93A2E5727","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b56a081284a600934b106424da428e697f11fda4","datavalue":{"value":{"entity-type":"item","numeric-id":4458593,"id":"Q4458593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517653$156444C4-A2B6-46C4-ADDE-E5C9C552D05D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d313e8d53726d4d29aec907c3cc3010b482d6562","datavalue":{"value":{"entity-type":"item","numeric-id":3356317,"id":"Q3356317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517653$7EF1C7B2-DED2-40A9-ACF2-823DE92547FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e4835be3618b612452b9df222b6f6d7bdecbf3e","datavalue":{"value":{"entity-type":"item","numeric-id":4387751,"id":"Q4387751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517653$4A26F1B2-E54D-4E2D-94E1-EA3CC9823C7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"298ef5d69d0899859f4551080d5281f2074896cd","datavalue":{"value":{"entity-type":"item","numeric-id":5311854,"id":"Q5311854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517653$CC409092-8FBA-46C3-B9FC-2B7AF7258152","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"ac8a9d49d4068fc47cabe0b3afdf45b5d1e20810","datavalue":{"value":"bafkreidvp6udon62vwzm2lt64jfeemqqgpgqxw3sj52say6kah2l2y2xxi","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2517653$01E09412-8E57-41C8-AE67-D83DB5343F68","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba81c20192f0bc62b1ebb855496feca8aee20c8c","datavalue":{"value":{"entity-type":"item","numeric-id":727195,"id":"Q727195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67f6c16df0bcdf327a64de76e102683e5178e679","datavalue":{"value":{"amount":"+0.8672834634780884","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":"Q2517653$C975577B-4532-45C5-B147-C47D306E6D81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a76203e19a474ac5488869af074b425604a58c84","datavalue":{"value":{"entity-type":"item","numeric-id":5109073,"id":"Q5109073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6722f9879379e718b8f4f3658bd69b2ea276bc4e","datavalue":{"value":{"amount":"+0.853136420249939","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":"Q2517653$79035232-CCA8-4CF6-B8C9-742258A47C06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13d8495881b038269af051b142b2871e8e6c7362","datavalue":{"value":{"entity-type":"item","numeric-id":3356317,"id":"Q3356317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3181e5db82f7f8240138da4f37b0fea92c6f3c60","datavalue":{"value":{"amount":"+0.8254088163375854","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":"Q2517653$2D3AC401-9393-4310-9C30-93D12E704587","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3f74d749c108b3a1f04cecde096a82a1afc253d","datavalue":{"value":{"entity-type":"item","numeric-id":1598840,"id":"Q1598840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61854ae27f905cf41185095028eaa22f0c6be87a","datavalue":{"value":{"amount":"+0.8241263628005981","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":"Q2517653$AD6DE94C-9AB5-4052-BE33-BF69CEEAA218","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18c8b50f4e3ae19c83eeaecd2880a75fd30590c6","datavalue":{"value":{"entity-type":"item","numeric-id":4329151,"id":"Q4329151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f815749c27694149bfdf040e48cbe12f5f259e4","datavalue":{"value":{"amount":"+0.8221343159675598","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":"Q2517653$B897B920-BFF5-4DEF-A509-790A3C82CD17","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Completing partial proper colorings using Hall's condition","badges":[]}}}}}