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$.

  • 1
    $\begingroup$ 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] $\endgroup$ – Mike Feb 10 '19 at 17:04
  • 1
    $\begingroup$ @Mike: I expect the answer to your question is “no” and that is why the OP phrased the question in terms of cardinality. $\endgroup$ – Anthony Quas Feb 10 '19 at 17:20
  • 1
    $\begingroup$ Thanks @Mike for your question, and as Anthony Quas writes, the question is about general infinite digraphs, no restriction on degrees $\endgroup$ – Dominic van der Zypen Feb 10 '19 at 18:17
  • 1
    $\begingroup$ Perhaps the title should say "majority coloring" instead of "directed coloring"? $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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 $\endgroup$ – Dominic van der Zypen Feb 12 '19 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.