| Naslov: | Brooks' type theorems for coloring parameters of locally finite graphs and Kőnig's Lemma |
|---|
| Avtorji: | ID Banerjee, Amitayu (Avtor)
ID Molnár, Zalán (Avtor)
ID Gopaulsingh, Alexa (Avtor) |
|---|
| Datoteke: |  RAZ_Banerjee,Molnar,Gopaulsingh_2025.pdf (562,21 KB)
MD5: D23F5F238E80C3A0B60071887811B248
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Članek v reviji |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | ZUP - Založba Univerze na Primorskem
|
|---|
| Opis: | 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. |
|---|
| Ključne besede: | Axiom of Choice, Kőnig's Lemma, Brooks’ theorem, distinguishing proper coloring, total coloring, list-distinguishing proper coloring |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 20.08.2025 |
|---|
| Založnik: | Založba Univerze na Primorskem |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | 24 str. |
|---|
| Številčenje: | Vol. 25, no. 4, [article no.] P4.06 |
|---|
| PID: | 20.500.12556/RUP-22019  |
|---|
| UDK: | 51 |
|---|
| eISSN: | 1855-3974 |
|---|
| DOI: | https://doi.org/10.26493/1855-3974.3453.4a8 |
|---|
| Datum objave v RUP: | 22.10.2025 |
|---|
| Število ogledov: | 334 |
|---|
| Število prenosov: | 2 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
