A Note About Majority Colorings of Countable DAGs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914827640766464 |
|---|---|
| author | Bosek, Bartłomiej Katan, Aleksander |
| author_facet | Bosek, Bartłomiej Katan, Aleksander |
| contents | A majority coloring of an undirected graph is a vertex coloring in which for each vertex there are at least as many bi-chromatic edges containing that vertex as monochromatic ones. It is known that for every countable graph a majority 3-coloring always exists. The Unfriendly Partition Conjecture states that every countable graph admits a majority 2-coloring. Since the 3-coloring result extends to countable DAGs, a variant of the conjecture states that 2 colors are enough to majority color every countable DAG. We show that this is false by presenting a DAG for which 3 colors are necessary. Presented construction is strongly based on a StackExchange conversation regarding labellings of infinite graphs that is linked in the references. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_04189 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Note About Majority Colorings of Countable DAGs Bosek, Bartłomiej Katan, Aleksander Discrete Mathematics Combinatorics 05C15, 05C63, 05C20 G.2.1 A majority coloring of an undirected graph is a vertex coloring in which for each vertex there are at least as many bi-chromatic edges containing that vertex as monochromatic ones. It is known that for every countable graph a majority 3-coloring always exists. The Unfriendly Partition Conjecture states that every countable graph admits a majority 2-coloring. Since the 3-coloring result extends to countable DAGs, a variant of the conjecture states that 2 colors are enough to majority color every countable DAG. We show that this is false by presenting a DAG for which 3 colors are necessary. Presented construction is strongly based on a StackExchange conversation regarding labellings of infinite graphs that is linked in the references. |
| title | A Note About Majority Colorings of Countable DAGs |
| topic | Discrete Mathematics Combinatorics 05C15, 05C63, 05C20 G.2.1 |
| url | https://arxiv.org/abs/2406.04189 |