# Majority coloring of infinite digraphs

## Main Article Content

## Abstract

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 http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1294/668
Issue

Section

EUROCOMB 2019