3
$\begingroup$

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

$\endgroup$
4
  • 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
    Commented Feb 10, 2019 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$ Commented Feb 10, 2019 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$ Commented Feb 10, 2019 at 18:17
  • 1
    $\begingroup$ Perhaps the title should say "majority coloring" instead of "directed coloring"? $\endgroup$
    – Dap
    Commented Feb 12, 2019 at 2:24

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
1
  • $\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$ Commented Feb 12, 2019 at 7:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .