Majority coloring of infinite digraphs

Marcin Anholcer , Bartłomiej Bosek , Jarosław Grytczuk


Let 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.
Author Marcin Anholcer (WIiGE / KBO)
Marcin Anholcer,,
- Department of Operations Research
, Bartłomiej Bosek - Uniwersytet Jagielloński w Krakowie (UJ)
Bartłomiej Bosek,,
, Jarosław Grytczuk - Warsaw University of Technology (PW), MNiSW [80]
Jarosław Grytczuk,,
Journal seriesActa Mathematica Universitatis Comenianae, ISSN 0231-6986, e-ISSN 0862-9544, (N/A 20 pkt)
Issue year2019
Publication size in sheets0.5
ConferenceEuropean Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2019), 26-08-2019 - 30-08-2019, Bratislava, Słowacja
Keywords in Polishdigraf, nieskończony digraf, kolorowanie większościowe, zasada zwartości
Keywords in Englishdigraph, infinite digraph, majority coloring, compactness principle
ASJC Classification2600 General Mathematics
Languageen angielski
Score (nominal)20
Score sourceconferenceList
ScoreMinisterial score = 20.0, 03-04-2020, ArticleFromConference
Publication indicators WoS Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 0.831
Citation count*2 (2021-06-14)
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?