Majority coloring of infinite digraphs
Marcin Anholcer , Bartłomiej Bosek , Jarosław Grytczuk
AbstractLet D be a finite or in finite digraph. A 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) <= 4 for any finite digraph D, and mu(D) <= 2 if D is acyclic. We prove that mu(D) <= 5 for any countably in finite digraph D, and mu(D) <= 3 if D does not contain finite directed cycles. We also state a twin supposition to the famous Unfriendly Partition Conjecture.
|Journal series||Acta Mathematica Universitatis Comenianae, ISSN 0231-6986, e-ISSN 0862-9544, (N/A 20 pkt)|
|Publication size in sheets||0.5|
|Conference||European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2019), 26-08-2019 - 30-08-2019, Bratislava, Słowacja|
|Keywords in Polish||digraf, nieskończony digraf, kolorowanie większościowe, zasada zwartości|
|Keywords in English||digraph, infinite digraph, majority coloring, compactness principle|
|Score||= 20.0, 03-04-2020, ArticleFromConference|
|Publication indicators||= 0; : 2018 = 0.831|
|Citation count*||2 (2020-08-04)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.