{"entities":{"Q2030755":{"pageid":2041497,"ns":120,"title":"Item:Q2030755","lastrevid":57681435,"modified":"2026-03-31T21:43:49Z","type":"item","id":"Q2030755","labels":{"en":{"language":"en","value":"Majority colorings of sparse digraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7356174"}},"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":"Q2030755$6CB15E18-7107-4693-8167-0293554E19A4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"292ecefc37f270ee817281611b0329a8276d406f","datavalue":{"value":{"text":"Majority colorings of sparse digraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2030755$A43E9CDB-4B46-468B-BAF5-6C203500C770","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2c91fb14bfbd66aad65c100ea4710c3b18d9ad6b","datavalue":{"value":"1465.05057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2030755$C89ADA45-4935-4C88-BE6C-6BB8EBC080C2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"be36f5f8b1eb9d830bb3141b03669d98ba740448","datavalue":{"value":"10.37236/10067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2030755$329D7604-D562-4407-8A0E-B6CE1CF2BFAB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2030755$A40844C9-C539-40BD-9C2A-AB7DE8F5C173","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":"Q2030755$0997715D-8B3B-4746-962E-D0B4176E0AD8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"de5072478c34efb4e89b692825659793fe4b3fb8","datavalue":{"value":{"time":"+2021-06-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2030755$8F236B87-BC2A-4C27-9021-E0BD4334DF4C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"064dfac6096bb2ccbcb66a0ffd25fc6ffdf22e96","datavalue":{"value":"https://arxiv.org/abs/1911.01954","type":"string"},"datatype":"url"},"type":"statement","id":"Q2030755$9E3E187F-F88F-47EA-B5D6-BC3AFC73E430","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c169f718f84e31fff6c888f18276ac4e1dbd2e4e","datavalue":{"value":"Summary: A majority coloring of a directed graph is a vertex-coloring in which every vertex has the same color as at most half of its out-neighbors. \\textit{S. Kreutzer} et al. [Electron. J. Comb. 24, No. 2, Research Paper P2.25, 9 p. (2017; Zbl 1364.05029)] proved that every digraph has a majority 4-coloring and conjectured that every digraph admits a majority 3-coloring. They observed that the Local Lemma implies the conjecture for digraphs of large enough minimum out-degree if, crucially, the maximum in-degree is bounded by an (exponential) function of the minimum out-degree.  Our goal in this paper is to develop alternative methods that allow the verification of the conjecture for natural, broad digraph classes, without any restriction on the in-degrees. Among others, we prove the conjecture 1) for digraphs with chromatic number at most 6 or dichromatic number at most \\(3\\), and thus for all planar digraphs; and 2) for digraphs with maximum out-degree at most 4. The benchmark case of \\(r\\)-regular digraphs remains open for \\(r \\in [5,143]\\). Our inductive proofs depend on loaded inductive statements about precoloring extensions of list-colorings. This approach also gives rise to stronger conclusions, involving the choosability version of majority coloring.  We also give further evidence towards the existence of majority-3-colorings by showing that every digraph has a fractional majority 3.9602-coloring. Moreover we show that every digraph with large enough minimum out-degree has a fractional majority \\((2+\\varepsilon)\\)-coloring.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2030755$9D5D26DF-77B5-44B6-AC8D-39436C5A332D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2030755$9F2FE02D-7567-41CB-A2DB-49C82960F5C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2030755$F18E463C-781F-45E0-8465-E42FA9919410","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cf979f4acdc6dac710cfd0a80dde6754b28a9043","datavalue":{"value":"05C42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2030755$5D03F44A-D268-46E6-A177-CF57FD227330","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2030755$B79DE06C-FD88-437B-9994-B0EEFC24AD33","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fb57cad43d308941f3ed4e97ff60588a853ed002","datavalue":{"value":"7356174","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2030755$043789F7-B3D1-474F-BABD-78902467FA96","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"787aa1108e12434165d3e5092ca6920dbd7bcfe9","datavalue":{"value":"fractional majority \\((2+\\varepsilon)\\)-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2030755$9BA6F0F1-136A-4E73-98EF-CD30164A07F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84aa50910ed4c3de061a0cc317c1cf3fb4687b13","datavalue":{"value":"minimum out-degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2030755$9376359B-0F7F-4F6A-A42C-5B0DF49B212E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6ee3819a7eca5b35aae8bc2e2d1304976db187f","datavalue":{"value":"maximum in-degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2030755$6960767B-93E5-4675-AA88-C20AA1FA6A48","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":"Q2030755$6657811C-D850-433A-B4F2-2331DBD294DC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b7f981dbc7f43daf2e9a3a07c5a7934634b8f45f","datavalue":{"value":"W3166274947","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2030755$09A9D5A6-D53A-4902-8AA2-3CA222CC5A3A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d46ea8c627f0eff0ab8e8e0c5f42111371366738","datavalue":{"value":{"entity-type":"item","numeric-id":1125942,"id":"Q1125942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2030755$8A76F814-AD3B-4DAD-B9EC-6216FECA3C16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbc468d3cc26a338143833e6ddc35850c0de0f64","datavalue":{"value":{"entity-type":"item","numeric-id":3419770,"id":"Q3419770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2030755$3E3804D1-C7CE-46B9-8A84-8B13D564E16E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19a30be36b741b5948b80df29f47a8fc7827c6c3","datavalue":{"value":{"entity-type":"item","numeric-id":5110646,"id":"Q5110646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2030755$8A2E2277-120D-48EE-9BB4-43B619B71E85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96c9663820a77e9d50078ee7903c43d5651c8e46","datavalue":{"value":{"entity-type":"item","numeric-id":1093650,"id":"Q1093650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2030755$09C01421-330C-4938-BB9B-03524D06736F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d8b11de2bf8db868d1f0d24e9a19548d5f9dd57","datavalue":{"value":{"entity-type":"item","numeric-id":2409821,"id":"Q2409821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2030755$62D103C0-C32A-4551-8946-3D742E3D44C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a6ad14495ffafa4a4179b24fa8c1468b9f9b91e","datavalue":{"value":{"entity-type":"item","numeric-id":1704574,"id":"Q1704574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2030755$853741DD-CFCB-409A-8054-847A4371556C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdd8eb669e06d011784a0fecc0db71fccb7d348b","datavalue":{"value":{"entity-type":"item","numeric-id":4638642,"id":"Q4638642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2030755$C9F71AEA-743C-4BC9-8197-30CBBFE70E09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90363de4ce41a81671f786b9da7266436d4ad4d8","datavalue":{"value":{"entity-type":"item","numeric-id":1684653,"id":"Q1684653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2030755$C80D28A4-1901-443F-8058-6DF73A1BD8EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61fed07a3ce0f935738863c4f8187484a8801148","datavalue":{"value":{"entity-type":"item","numeric-id":5373832,"id":"Q5373832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2030755$082D9E02-8F7B-4972-BEA3-1D18EAAC067B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58c7de81e8a6f1a41d779ae6a8db6b8312d3dcd6","datavalue":{"value":{"entity-type":"item","numeric-id":1671650,"id":"Q1671650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2030755$A10D53E0-491E-4FAE-95FF-2613A2496303","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":"Q2030755$A7A5809B-16AE-4F45-95E6-C08B6CD4D71A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c3ed573aab1340e3f01f3d7d04ea69b64bec434","datavalue":{"value":{"entity-type":"item","numeric-id":1836671,"id":"Q1836671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2030755$652148F7-A8BC-41A2-98A5-41624D9041F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d86037c0a27df7454ce818775674854b0229616","datavalue":{"value":{"entity-type":"item","numeric-id":1865419,"id":"Q1865419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2030755$F75B182E-A61F-4B80-B3B1-815F3AF00E0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08b8b9a77b27cf689aeded7f2686dca7ff8c090e","datavalue":{"value":{"entity-type":"item","numeric-id":4135588,"id":"Q4135588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2030755$D060921E-4C16-408D-AB60-F163015E0CF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11d668b2b0cd9a6e9f2d6029bb0c14d12192a081","datavalue":{"value":{"entity-type":"item","numeric-id":1750217,"id":"Q1750217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2030755$03C09471-0584-4480-9BBB-79282AF4B378","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"8cbf9c53fc2af8e4ca81902b656ad028098ed2ee","datavalue":{"value":"bafkreiggxajf4hgdjlye6krbcvwzct5g4q4ytgvbfcc2p72iqd6pivp7ea","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2030755$83AB82D7-3C3B-4226-BA35-6396098F2891","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f932cf880f4ba90b78fbb41c273bf618ec431cf","datavalue":{"value":{"entity-type":"item","numeric-id":2409821,"id":"Q2409821"},"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":"Q2030755$52E4A3B9-1057-4788-91EC-E2A193E06456","rank":"normal"},{"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":"d143bb6cc97967f40f3fd4f0f1cceeb355b71fcc","datavalue":{"value":{"amount":"+0.8995946645736694","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":"Q2030755$C7694A57-7FC1-427A-BC8F-FE5E300C9091","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":"9c9658ee3d065067191881a1cd9142550a8a32af","datavalue":{"value":{"amount":"+0.8986741900444031","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":"Q2030755$1D4FA5F0-1CFB-48BC-8E0B-EE072482119E","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":"eff0d87664edb26588bc1a32fddef97d518eafed","datavalue":{"value":{"amount":"+0.884070634841919","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":"Q2030755$10463970-0051-456E-9015-DB99C755291E","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":"1bcd921224a4213ede1fecd205d846fa6a7866a2","datavalue":{"value":{"amount":"+0.8165637850761414","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":"Q2030755$DA428A00-0B21-408C-B85E-314C60F8E5D2","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2030755$88F91263-7E55-434A-A5CC-DCA973F365C2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2030755","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2030755"}}}}}