Brooks' type theorems for coloring parameters of locally finite graphs and Konig's Lemma
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908539021164544 |
|---|---|
| author | Banerjee, Amitayu Molnár, Zalán Gopaulsingh, Alexa |
| author_facet | Banerjee, Amitayu Molnár, Zalán Gopaulsingh, Alexa |
| contents | In the past, analogues to Brooks' theorem have been found for various parameters of graph coloring for infinite locally finite connected graphs in ZFC. We prove these theorems are not provable in ZF (i.e. the Zermelo-Fraenkel set theory without the Axiom of Choice (AC)). Moreover, such theorems follow from Konig's Lemma (every infinite locally finite connected graph has a ray-a weak form of AC) in ZF. In ZF, we formulate new conditions for the existence of the distinguishing chromatic number, the distinguishing chromatic index, the total chromatic number, the total distinguishing chromatic number, the odd chromatic number, and the neighbor-distinguishing index in infinite locally finite connected graphs, which are equivalent to Konig's Lemma. In this direction, we strengthen a recent result of Stawiski from 2023.
We also figured out the upper bound for list-distinguishing chromatic number for infinite graphs in ZFC (i.e. the Zermelo-Fraenkel set theory with the Axiom of Choice (AC)). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_00812 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Brooks' type theorems for coloring parameters of locally finite graphs and Konig's Lemma Banerjee, Amitayu Molnár, Zalán Gopaulsingh, Alexa Combinatorics Logic 03E25, 05C63, 05C15, 05C25 In the past, analogues to Brooks' theorem have been found for various parameters of graph coloring for infinite locally finite connected graphs in ZFC. We prove these theorems are not provable in ZF (i.e. the Zermelo-Fraenkel set theory without the Axiom of Choice (AC)). Moreover, such theorems follow from Konig's Lemma (every infinite locally finite connected graph has a ray-a weak form of AC) in ZF. In ZF, we formulate new conditions for the existence of the distinguishing chromatic number, the distinguishing chromatic index, the total chromatic number, the total distinguishing chromatic number, the odd chromatic number, and the neighbor-distinguishing index in infinite locally finite connected graphs, which are equivalent to Konig's Lemma. In this direction, we strengthen a recent result of Stawiski from 2023. We also figured out the upper bound for list-distinguishing chromatic number for infinite graphs in ZFC (i.e. the Zermelo-Fraenkel set theory with the Axiom of Choice (AC)). |
| title | Brooks' type theorems for coloring parameters of locally finite graphs and Konig's Lemma |
| topic | Combinatorics Logic 03E25, 05C63, 05C15, 05C25 |
| url | https://arxiv.org/abs/2408.00812 |