Skip to main content
1 of 2

Majority coloring for directed graphs

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. I'm not sure how to reach higher majority coloring numbers, and even for tournaments on $n$ vertices, I'm not sure when this number is $2$, and when it's larger than $2$.