Majority coloring for directed graphs

Question

I came up with the following coloring concept when studying neural networks (which are often modelled using directed graphs). No idea whether there is already an established name for it.

If $X$ is a non-empty set, we say that $M\subseteq X$ is a majority if $|M| > |X\setminus M|$.

Let $G=(V,E)$ be a finite directed graph. For $v\in V$ we set $\text{In}(v)=\{x \in V: (x,v) \in E\}$.

Let $n$ be a positive integer. We say that a map $c:V(G) \to \{1,\ldots,n\}$ is a majority coloring if the following condition is satisfied:

For every $v\in V(G)$ with $\text{In}(v) \neq \emptyset$, if for some $k \in \{1,\ldots, n\}$ we have that $c^{-1}(\{k\}) \cap \text{In}(v)$ is a majority of $\text{In}(v)$, then $c(v) \neq k$.

We set the majority coloring number $\chi_m(G)$ to be the least positive integer $j$ such that there is a majority coloring $c:V(G) \to \{1,\ldots,j\}$.

Many directed graphs I've looked at have majority coloring number $2$, but for instance $K_3$ with the orientation $1\to 2\to 3\to 1$ has majority coloring number $3$.

Questions:

1. For $n\in\mathbb{N}$ is there a directed graph $G$ such that $\chi_m(G) = n$?
2. For $n\in\mathbb{N}$ is there even a tournament $T$ such taht $\chi_m(T) = n$?

Answer 1

Let me answer Question 2. The answer is in negative: there exists an upper bound for majority coloring numbers of all tournaments. I will not care about the sharpness of the bound.

Let $G$ be a tournament on $n$ vertices, and let $d_1\leq d_2\leq \dots\leq d_n$ be the in-degrees of its vertices (denote the vertices $v_1,\dots,v_n$ respectively). We want to find its majority coloring in $3k$ colors.

Firstly, notice that the first $m$ vertices induce a sub-tournament with $m\choose 2$ edges. This means that $d_1+\dots+d_m\geq {m\choose 2}$, which yields $d_m\geq \frac{m-1}2$. Now we paint $v_1,\dots,v_{2k}$ with the last $2k$ colors; all the remaining vertices will be painted with the first $k$ colors, so the conditions for $v_1,\dots,v_{2k}$ are satisfied automatically.

Each of the remaining vertices has in-degree at least $k$. Consider a random coloring of them in $k$ colors. Now, for each $i>2k$, the probability $p_i$ that at least half of $\mathop{\rm In}(v_i)$ are painted with the color of $v_i$ can be bounded by Hoeffding's inequality as $$ p_i\leq \exp\left(-2\left(\frac12-\frac1k\right)^2 d_i\right)^2 \leq \exp\left(-\frac{(k-2)^2}{2k^2}(i-1)\right) $$ (the estimate may become even better if $\mathop{\rm In}(v_i)$ contains some of the first $2k$ vertices). So the probability that at least one vertex violates the required condition does not exceed $$ \sum_{i=2k+1}^n p_i \leq \sum_{i=2k+1}^n \exp\left(-\frac{(k-2)^2}{4k^2}(i-1)\right) <\sum_{j=2k}^\infty \exp\left(-\frac{(k-2)^2}{4k^2}j\right)\\ =\exp\left(-\frac{k(k-2)^2}{4k^2}\right)\cdot \left(1-\exp\left(-\frac{(k-2)^2}{4k^2}\right)\right)^{-1}. $$ This last bound tends to $0$ as $k\to\infty$, so it is less than $1$ for some value of $k$. This value fits.

Remarks. 1. One may try to improve this estimate by making something different with the vertices of low in-degree, e.g., introducing them into a general scheme and computing the sharp values of $p_i$ for these vertices. However, I doubt that a sharp bound may be obtained in this way.

2. The estimates from the beginning do not work for arbitrary digraphs. However, we may see some conditions a hypothetical example should satisfy.

Firstly, a minimal example should not contain vertices of low total degree, since one may color the graph without such vertex, and then paint it with a color different from all its neighbors' colors. On the other hand, this graph should contain many vertices of relatively small in-degree, since otherwise the estimate using Hoeffding's inequality would work.

Answer 2

According to this link (see point $15$), Matt DeVos and David Wood can prove that every digraph in which each vertex has an out-neighbour has a good $4$-colouring (I am using their terminology).

Update. The paper Majority Colourings of Digraphs by Kreutzer, Oum, Seymour, van der Zypen (the OP), and Wood is now available on the arXiv. They give a short proof for $4$ colours and provide evidence for the conjecture with $3$ colours.

Answer 3

The paper mentioned above has been published:

Stephan Kreutzer, Sang-il Oum, Paul Seymour, Dominic van der Zypen, David R. Wood. "Majority Colourings of Digraphs" Electronic Journal of Combinatorics, 24(2):#P2.25, 2017. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p25

Other papers have appeared on this topic:

Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk. "Every digraph is majority 4-choosable" http://arxiv.org/abs/1608.06912

Fiachra Knox, Robert Šámal. "Linear Bound for Majority Colourings of Digraphs" https://arxiv.org/abs/1701.05715

A. Girao, T. Kittipassorn, and K. Popielarz. "Generalised majority colourings of digraphs" https://arxiv.org/abs/1701.03780