%A Anholcer, Marcin
%A Bosek, BartÅ‚omiej
%A Grytczuk, JarosÅ‚aw
%D 2019
%T Majority coloring of infinite digraphs
%K
%X 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.
%U http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1294
%J Acta Mathematica Universitatis Comenianae
%0 Journal Article
%P 371-376%V 88
%N 3
%@ 0862-9544
%8 2019-07-26