{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T15:35:48Z","timestamp":1775835348565,"version":"3.50.1"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>A majority coloring\u00a0of a directed graph is a vertex-coloring in which every vertex has the same color as at most half of its out-neighbors. Kreutzer, Oum, Seymour, van der Zypen and Wood 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 a(n exponential) function of the minimum out-degree.\r\nOur goal in this paper is to develop alternative methods that allow the verification of the conjecture for natural, broad digraph classes, without\u00a0any 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]$.\r\nOur 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.\r\nWe 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.<\/jats:p>","DOI":"10.37236\/10067","type":"journal-article","created":{"date-parts":[[2021,6,8]],"date-time":"2021-06-08T09:20:37Z","timestamp":1623144037000},"source":"Crossref","is-referenced-by-count":5,"title":["Majority Colorings of Sparse Digraphs"],"prefix":"10.37236","volume":"28","author":[{"given":"Michael","family":"Anastos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ander","family":"Lamaison","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raphael","family":"Steiner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tibor","family":"Szab\u00f3","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2021,6,4]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v28i2p31\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v28i2p31\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,8]],"date-time":"2021-06-08T09:20:38Z","timestamp":1623144038000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v28i2p31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,4]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,4,9]]}},"URL":"https:\/\/doi.org\/10.37236\/10067","relation":{},"ISSN":["1077-8926"],"issn-type":[{"value":"1077-8926","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,4]]},"article-number":"P2.31"}}