Majority coloring of infinite digraphs

Main Article Content

Marcin Anholcer Bartłomiej Bosek Jarosław Grytczuk


Let $D$ be a finite or infinite digraph. A \emph{majority coloring} of $D$ is a vertex coloring such that at least half of the out-neighbors of every vertex $v$ have different color than $v$. Let $\mu(D)$ denote the least number of colors needed for a majority coloring of $D$. It is known that $\mu(D)\leq 4$ for any finite digraph $D$, and $\mu(D)\leq 2$ if $D$ is acyclic. We prove that $\mu(D)\leq 5$ for any countably infinite digraph $D$, and $\mu(D)\leq 3$ if $D$ does not contain finite directed cycles. We also state a twin supposition to the famous Unfriendly Partition Conjecture.

Article Details

How to Cite
Anholcer, M., Bosek, B., & Grytczuk, J. (2019). Majority coloring of infinite digraphs. Acta Mathematica Universitatis Comenianae, 88(3), 371-376. Retrieved from