Every finite directed graph has a [majority coloring with $4$ colors](https://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p25/pdf). (The notion of majority coloring is defined below.)


**Question.** Can every infinite directed graph be majority-colored with $4$ colors?




---


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 directed graph. For $v\in V$ we set $\text{In}(v)=\{x \in V: (x,v) \in E\}$.


Let $\kappa\neq \emptyset$ be a cardinal. We say that a map $c:V(G) \to \kappa$ 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 \kappa$ we have that $c^{-1}(\{k\}) \cap \text{In}(v)$ is a majority of $\text{In}(v)$, then $c(v) \neq k$.
> 
> 
> 



Does every directed graph have a directed coloring with $4$ colors?
Yes,$\DeclareMathOperator{In}{In}$ this seems to be true. Let $\deg^-(v)$ denote in-degree of $v$ and let $V$ denote the vertex set. We can partition $V$ as $V\_f\cup V\_<\cup V\_{\geq}$ where:


* $V\_f$ is the set of vertices $v$ with finite in-degree
* $V\_<$ is the set of vertices $v$ with infinite in-degree and $|\{u\in \In(v)\mid \deg^-(u)<\deg^-(v)\}|=\deg^-(v)$
* $V\_{\geq}$ is the set of vertices not in the above two sets


The idea is then to try to find a majority coloring in the set
$$C=\{c:V\to\{1,2,3,4\}\mid c(V\_<)\subseteq\{1,2\}\text{ and }c(V\_\geq)\subseteq\{3,4\}\}.$$


To color $V\_f$ we can apply compactness/Rado's selection principle similar to the de Bruijn–Erdős theorem, to reduce to the following statement about finite digraphs.



> 
> Given a finite digraph with some "adversary" sources labelled $\{1,2\}$ or $\{3,4\},$ there is a coloring $c$ of the non-adversary vertices such that for every extension of $c$ to a coloring $c'$ of the whole vertex set such that $c'(v)\in S$ for each adversary source $v$ labelled $S,$ the coloring $c$ is a majority coloring.
> 
> 
> 


*Proof:* This is a slight variant of the argument in "Majority Colourings of Digraphs". Order the vertices in any way such that the adversary vertices go after the non-adversary vertices. Go from left to right (low to high) coloring the non-adversary vertices "$\{1,3\}$" or "$\{2,4\}$" ensuring that $v$ does not get the same color as a majority of the vertices in $\In(v)$ to the left of $v.$ Go from right to left coloring the non-adversary vertices "$\{1,2\}$" or "$\{3,4\}$" ensuring that $v$ does not get the same color as a majority of the vertices in $\In(v)$ to the right of $v,$ including the labels from adversary vertices. Combining these two colors gives a value in $\{1,2,3,4\}$ at each non-adversary vertex meeting the requirements. $\Box$


Let $P$ be the set of pairs $(U,c)$ with $V\_f\subseteq U\subseteq V$ and $c:U\to\{1,2,3,4\}$ such that every extension of $c$ to $c'\in C$ satisfies the majority coloring condition at $v$ for each $v\in U.$
By the previous argument and compactness there is a pair $(V\_f,c)\in P.$ 
The set $P$ is chain-complete with the ordering of partial functions, $(U,c)\leq (U',c')$ if $U\subseteq U'$ and $c'|\_U=c.$ By Zorn's lemma there is a maximal pair $(U,c)\in P.$


Suppose that $V\_<\setminus U$ is non-empty. Pick an element $v$ of minimum in-degree. All $\deg^-(v)$ vertices in $\{u\in \In(v)\mid \deg^-(u)<\deg^-(v)\}$ are in $U\cup V\_\geq.$ So we know that in any coloring in $C$ extending $c,$ each of these vertices will be colored either $1$ or $2$ or something in $\{3,4\},$ though it is not necessarily determined which are 3 and which are 4. Still, we can choose either $1$ or $2$ not matching a majority of the vertices in $\In(v).$ Extending $c$ by this choice of $c(v)$ gives a larger coloring contradicting maximality.


By a similar argument, for all $v\in V\setminus U$ there are fewer than $\deg^-(v)$ vertices of $\In(v)$ in $U.$ This means that $(U,c)$ is irrelevant when coloring vertices not in $U.$


Suppose there exists $v\in V\setminus U\subseteq V\_\geq.$ Let $W$ be the set of all vertices $w\in V\setminus U$ such that there is a directed path from $w$ to $v,$ through vertices in $V\setminus U.$
We will try to find a coloring $\hat{c}:W\to\{3,4\}$ such that $|\hat{c}^{-1}(\{k\})\cap\In(w)|=\deg^-(w)$ for each $k\in\{3,4\}$ and $w\in W.$ 
Let $W\_\kappa=\{w\in W\mid \deg^-(w)= \kappa\}$ for each cardinal $\kappa\geq \deg^-(v).$ The induced subdigraph on $\bigcup\_{\lambda\leq\kappa}W\_\lambda$ has all in-degrees at most $\kappa,$ and every vertex has a directed path to the sink $v.$ Therefore $|W\_\kappa|\leq \kappa.$
So $\{\In(w)\cap W\mid w\in W\_\kappa\}$ is a family of at most $\kappa$ sets of order $\kappa.$ For each $\kappa$ such that $W\_\kappa\neq\emptyset,$ starting with the smallest, by transfinite induction we can color $\bigcup\{\In(w)\cap W\mid w\in W\_\kappa\}$ using colors in $\{3,4\}$ such that $|\hat{c}^{-1}(\{k\})\cap\In(w)|=\kappa$ for $w\in W\_\kappa$ - just use a bijection $\kappa\to W\_\kappa\times\kappa$ to make sure that at each step fewer than $\kappa$ vertices are already colored.


This shows that a maximal element of $P$ actually colors the whole vertex set.


