English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A majority coloring of a directed graph is a vertex-coloring in which everyvertex 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 majority4-coloring and conjectured that every digraph admits a majority 3-coloring. Weverify this conjecture for digraphs with chromatic number at most 6 ordichromatic number at most 3. We obtain analogous results for list coloring: Weshow that every digraph with list chromatic number at most 6 or listdichromatic number at most 3 is majority 3-choosable. We deduce that digraphswith maximum out-degree at most 4 or maximum degree at most 7 are majority3-choosable. On the way to these results we investigate digraphs admitting amajority 2-coloring. We show that every digraph without odd directed cycles ismajority 2-choosable. We answer an open question posed by Kreutzer et al.negatively, by showing that deciding whether a given digraph is majority2-colorable is NP-complete. Finally we deal with a fractional relaxation ofmajority coloring proposed by Kreutzer et al. and show that every digraph has afractional majority 3.9602-coloring. We show that every digraph with minimumout-degree $\Omega\left((1/\varepsilon)^2\ln(1/\varepsilon)\right)$ has afractional majority $(2+\varepsilon)$-coloring.

Majority Colorings of Sparse Digraphs