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](https://en.wikipedia.org/wiki/Tournament_(graph_theory)) $T$ such taht $\chi\_m(T) = n$?



Majority coloring for directed graphs
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.


