Majority coloring of infinite digraphs

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

Abstract

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
Vol88
No3
Pages371-376
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
URL http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1294
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 (2020-08-04)
Cite
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.
Back
Confirmation
Are you sure?