# Does every directed graph have a directed coloring with $4$ colors?

Every finite directed graph has a majority coloring with $$4$$ colors. (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$$.

• Do you require every vertex to have finite degree? [Suppose that $v$ has infinite indegree and there are an infinite number of neighbours in In$(v)$ colored each of the four colors] – Mike Feb 10 '19 at 17:04
• @Mike: I expect the answer to your question is “no” and that is why the OP phrased the question in terms of cardinality. – Anthony Quas Feb 10 '19 at 17:20
• Thanks @Mike for your question, and as Anthony Quas writes, the question is about general infinite digraphs, no restriction on degrees – Dominic van der Zypen Feb 10 '19 at 18:17
• Perhaps the title should say "majority coloring" instead of "directed coloring"? – Dap Feb 12 '19 at 2:24

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.

• Thanks for your nice answer! This result might be publishable as a short note. If you are interested in a collaboration, please drop me a line at dominic.zypen at gmail dot com – Dominic van der Zypen Feb 12 '19 at 7:55