{"entities":{"Q2409821":{"pageid":2420564,"ns":120,"title":"Item:Q2409821","lastrevid":57908238,"modified":"2026-04-03T01:15:39Z","type":"item","id":"Q2409821","labels":{"en":{"language":"en","value":"Majority choosability of digraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6791406"}},"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":"Q2409821$70379F8E-96D9-424B-BA30-88D68C8372D0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7abc07813136ada65b2de2693c9909cc5feea2b4","datavalue":{"value":{"text":"Majority choosability of digraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2409821$A5DCEB6A-E327-430C-AFD3-FC4457606428","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"80b867b4e3ccd4ba2c31f6b2c951b905e84a9c4f","datavalue":{"value":"1375.05079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409821$0863EAE4-3F5F-413B-B8AC-571405350F8B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3fa23ab3975128562ad434cfb6f83dedda34803a","datavalue":{"value":{"entity-type":"item","numeric-id":268263,"id":"Q268263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409821$D088F78B-558B-4DA4-A5AE-D05FB4960E4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"01ff5be92d121f7423ad3cd6c581778876c098c4","datavalue":{"value":{"entity-type":"item","numeric-id":251889,"id":"Q251889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409821$E4F92FB2-E8D9-4207-A15D-3A2549A8346E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9efe106b3c39b129b376e8258a66132030c4b918","datavalue":{"value":{"entity-type":"item","numeric-id":282742,"id":"Q282742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409821$C1515898-BB8E-4906-9B84-578FB5262BEE","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":"Q2409821$E9B5D277-EB75-41D1-89D4-A7B0F750DD1C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6c5297401e02788bd3f4d1f30d634c2fb25880e4","datavalue":{"value":{"time":"+2017-10-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2409821$66CED2E2-6036-4EAF-B509-D23CE224AE60","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3f1880bb06944362440f0da5e41b19d0a90d7624","datavalue":{"value":"https://arxiv.org/abs/1608.06912","type":"string"},"datatype":"url"},"type":"statement","id":"Q2409821$EED2E2F4-18F2-421A-B84D-C14406A2E5F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"4979b6380300d3a63454a03932a93ebe01a116d4","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p57","type":"string"},"datatype":"url"},"type":"statement","id":"Q2409821$46BF4A65-DEE1-4D32-B5E5-D38C49146182","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f3ee9a570e804949569e4ea8e7e2387cfc3a7f4a","datavalue":{"value":"Summary: A \\textit{majority coloring} of a digraph is a coloring of its vertices such that for each vertex \\(v\\), at most half of the out-neighbors of \\(v\\) have the same color as \\(v\\). A digraph \\(D\\) is \\textit{majority \\(k\\)-choosable} if for any assignment of lists of colors of size \\(k\\) to the vertices there is a majority coloring of \\(D\\) from these lists. We prove that every digraph is majority \\(4\\)-choosable. This gives a positive answer to a question posed recently by \\textit{S. Kreutzer} et al. [ibid. 24, No. 2, Research Paper P2.25, 9 p. (2017; Zbl 1364.05029)]. We obtain this result as a consequence of a more general theorem, in which majority condition is profitably extended. For instance, the theorem implies also that every digraph has a coloring from arbitrary lists of size three, in which at most \\(2/3\\) of the out-neighbors of any vertex share its color. This solves another problem posed by the same authors, and supports an intriguing conjecture stating that every digraph is majority \\(3\\)-colorable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2409821$09E98830-48F0-469D-A516-53759D29E6D9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409821$A2EDB7EA-E028-416F-8582-CE40E804AEA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409821$AB1218CD-09F8-4A6F-A672-3903983780ED","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"01bbea8a2e40313cb1a035299168b0554f7d609b","datavalue":{"value":"6791406","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409821$13C15040-CFC1-4901-9F74-7705470A9EBC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf4dc3db86d44e89a36d3ec12340c2571d04f06","datavalue":{"value":"graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q2409821$16F5DB71-EBB3-48EA-A737-0EEC943F7275","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2409821$6ACD3AE9-89EE-4B71-AA0C-1C77A2B2D0A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5f6aefdf1ffec3bc08d67d0b64a04330c0d9134","datavalue":{"value":"list coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2409821$9DE64132-6DFF-445E-897E-4FCFC565901A","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":"Q2409821$DFE4E26E-3A1D-4AAE-9B12-109E6AE34B3A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3347058ad1e4b2819aa42d0c5844ce1a51a63bc2","datavalue":{"value":{"entity-type":"item","numeric-id":753841,"id":"Q753841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409821$9F20A565-1DE8-4F45-A690-3C7EDF32B038","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7011412e0799c283ed6405860711ef7fdab1df8c","datavalue":{"value":{"entity-type":"item","numeric-id":2628255,"id":"Q2628255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409821$87DC4D75-D018-4865-944B-59DBE5E56FAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74074974e02935f8f5ecb942cc6fe70f08b746ea","datavalue":{"value":{"entity-type":"item","numeric-id":5530470,"id":"Q5530470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409821$F5EE52EC-CD5E-4800-82CC-DEB9081F18FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"245abb3a90f1500c3f27160e6c2ee2204c5ca560","datavalue":{"value":{"entity-type":"item","numeric-id":4053703,"id":"Q4053703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409821$EFC2D093-2FF2-47A4-96B3-0E5B992A4084","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3da945c32c56855dbbf6788927dac5cddfa74242","datavalue":{"value":{"entity-type":"item","numeric-id":3211331,"id":"Q3211331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409821$3D1352F2-BE4F-4CE6-A7A5-0D017C28EF2B","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"fb95863e8d3ad154a55a2924338451209c533acc","datavalue":{"value":"bafkreifb4ktmu5mzldp3656onuf5ua4uejse2jlzuxrfrqcr5mpf67ux2y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409821$FD5D036E-A4A3-485C-A3E0-0A1549405BCB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38122eb3ba2b20dbd46f626548fdae609226c6eb","datavalue":{"value":{"entity-type":"item","numeric-id":5373832,"id":"Q5373832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b437f76080c484222b23fc98aa82bbf8f1079d6","datavalue":{"value":{"amount":"+0.9255874752998352","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":"Q2409821$30812672-2F30-46E4-AF55-1DA6CB16D62C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0fe417b437fc48b317dca10ebbb98830ccfb703","datavalue":{"value":{"entity-type":"item","numeric-id":2030755,"id":"Q2030755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72a6878b440a80ba3018190b8403294d17cb66d2","datavalue":{"value":{"amount":"+0.9204483032226562","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":"Q2409821$BA71B04B-8908-4917-B16F-8BF23B86C658","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ab56d8d3b3e091c677e98c03ac53775130505c3","datavalue":{"value":{"entity-type":"item","numeric-id":1671650,"id":"Q1671650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"996f394f8ce829a0386174374e0140cc2d8dbbdd","datavalue":{"value":{"amount":"+0.914623498916626","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":"Q2409821$BDC5F166-9EF2-451E-AF65-D613136AB10D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81a86f13c49adb485969306dd50a20a5b140e451","datavalue":{"value":{"entity-type":"item","numeric-id":2628255,"id":"Q2628255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e1ab1e1d5a634785afd5a6f68919490e2a243dc","datavalue":{"value":{"amount":"+0.892753541469574","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":"Q2409821$CDD52789-FB4B-43EB-A88B-28C0968D3C2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b0bc25df93464b7fbbec011aa07e38b3f3b4823","datavalue":{"value":{"entity-type":"item","numeric-id":2692181,"id":"Q2692181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e54a86d273f4c342f15cf4be7596f0810d1d4f3","datavalue":{"value":{"amount":"+0.8087882995605469","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":"Q2409821$A23FADFD-72E1-4502-8145-4BB5986ED15A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2409821","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2409821"}}}}}