Jagiellonian University Repository

Majority coloring of infinite digraphs


Majority coloring of infinite digraphs

Show full item record

dc.contributor.author Anholcer, Marcin pl
dc.contributor.author Bosek, Bartłomiej [SAP11019936] pl
dc.contributor.author Grytczuk, Jarosław pl
dc.date.accessioned 2020-01-09T13:44:02Z
dc.date.available 2020-01-09T13:44:02Z
dc.date.issued 2019 pl
dc.identifier.issn 0862-9544 pl
dc.identifier.uri https://ruj.uj.edu.pl/xmlui/handle/item/130287
dc.language eng pl
dc.rights Dodaję tylko opis bibliograficzny *
dc.rights.uri *
dc.title Majority coloring of infinite digraphs pl
dc.type JournalArticle pl
dc.description.physical 371-376 pl
dc.identifier.weblink http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1294/668 pl
dc.abstract.en 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. pl
dc.description.volume 88 pl
dc.description.number 3 pl
dc.identifier.eissn 1336-0310 pl
dc.title.journal Acta Mathematica Universitatis Comenianae pl
dc.language.container eng pl
dc.date.accession 2019-11-18 pl
dc.affiliation Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej pl
dc.subtype Article pl
dc.rights.original bez licencji pl
dc.identifier.project 2015/17/B/ST1/02660 pl
dc.identifier.project ROD UJ / O pl
.pointsMNiSW [2019 A]: 20

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)