Geodesic
Majority coloring of infinite digraphs
Marcin Anholcer1 ; Bartłomiej Bosek2 ; Jarosław Grytczuk3 ; Marcin Anholcer ; Bartłomiej Bosek ; Jarosław Grytczuk
1Faculty of Informatics and Electronic Economy, Poznań University of Economics and Business, Poznań , Poland
2Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland
3Faculty of Mathematics and Information Science, Warsaw University of Technology, Warsaw, Poland
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 371-376 
Marcin Anholcer; Bartłomiej Bosek; Jarosław Grytczuk; Marcin Anholcer; Bartłomiej Bosek; Jarosław Grytczuk. Majority coloring of infinite digraphs. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 371-376. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a2/
@article{AMUC_2019_88_3_a2,
     author = {Marcin Anholcer and Bart{\l}omiej Bosek and Jaros{\l}aw Grytczuk and Marcin Anholcer and Bart{\l}omiej Bosek and Jaros{\l}aw Grytczuk},
     title = { Majority coloring of infinite digraphs},
     journal = {Acta mathematica Universitatis Comenianae},
     pages = {371--376},
     year = {2019},
     volume = {88},
     number = {3},
     url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a2/}
}
TY  - JOUR
AU  - Marcin Anholcer
AU  - Bartłomiej Bosek
AU  - Jarosław Grytczuk
AU  - Marcin Anholcer
AU  - Bartłomiej Bosek
AU  - Jarosław Grytczuk
TI  - Majority coloring of infinite digraphs
JO  - Acta mathematica Universitatis Comenianae
PY  - 2019
SP  - 371
EP  - 376
VL  - 88
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a2/
ID  - AMUC_2019_88_3_a2
ER  - 
%0 Journal Article
%A Marcin Anholcer
%A Bartłomiej Bosek
%A Jarosław Grytczuk
%A Marcin Anholcer
%A Bartłomiej Bosek
%A Jarosław Grytczuk
%T Majority coloring of infinite digraphs
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 371-376
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a2/
%F AMUC_2019_88_3_a2

Voir la notice de l'article provenant de la source Comenius University

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.