| Title: | Brooks' type theorems for coloring parameters of locally finite graphs and Kőnig's Lemma |
|---|
| Authors: | ID Banerjee, Amitayu (Author)
ID Molnár, Zalán (Author)
ID Gopaulsingh, Alexa (Author) |
|---|
| Files: |  RAZ_Banerjee,Molnar,Gopaulsingh_2025.pdf (562,21 KB)
MD5: D23F5F238E80C3A0B60071887811B248
|
|---|
| Language: | English |
|---|
| Work type: | Article |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | ZUP - University of Primorska Press
|
|---|
| Abstract: | 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 that there is a model of ZF (i.e., the Zermelo–Fraenkel set theory without the Axiom of Choice (AC)) where these theorems fail. Moreover, such theorems follow from Kőnig’s Lemma (every infinite locally finite connected graph has a ray–a weak form of AC) in ZF. In ZF, inspired by a combinatorial argument of Herrlich and Tachtsis from 2006, 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 Kőnig’s Lemma.
In this direction, we strengthen a recent result of Stawiski from 2023. We also generalize an algorithm of Imrich, Kalinowski, Pilśniak, and Shekarriz to show that the statement “If G is a connected infinite graph where the maximum degree Δ(G) ≥ 3 is finite, then the list-distinguishing chromatic number is at most 2Δ(G) − 1” holds under Kőnig’s Lemma in ZF. However, we prove that there is a model of ZF where the above statement fails. |
|---|
| Keywords: | Axiom of Choice, Kőnig's Lemma, Brooks’ theorem, distinguishing proper coloring, total coloring, list-distinguishing proper coloring |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 20.08.2025 |
|---|
| Publisher: | Založba Univerze na Primorskem |
|---|
| Year of publishing: | 2025 |
|---|
| Number of pages: | 24 str. |
|---|
| Numbering: | Vol. 25, no. 4, [article no.] P4.06 |
|---|
| PID: | 20.500.12556/RUP-22019  |
|---|
| UDC: | 51 |
|---|
| eISSN: | 1855-3974 |
|---|
| DOI: | https://doi.org/10.26493/1855-3974.3453.4a8 |
|---|
| Publication date in RUP: | 22.10.2025 |
|---|
| Views: | 331 |
|---|
| Downloads: | 2 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
