Majority colorings of sparse digraphs

Michael Anastos¹ ; Ander Lamaison² ; Raphael Steiner ; Tibor Szabó¹

¹Freie Universität Berlin
²Masaryk University Brno

The electronic journal of combinatorics, Tome 28 (2021) no. 2

Résumé

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. 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. 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.

Détail

DOI : 10.37236/10067

Classification : 05C15, 05C20, 05C42, 05C75
Mots-clés : fractional majority \((2+\varepsilon)\)-coloring, minimum out-degree, maximum in-degree