20.500.12556/RUP-22019 Brooks' type theorems for coloring parameters of locally finite graphs and Kőnig's Lemma Brooksovi tipi izrekov za barvne parametre lokalno končnih grafov in Kőnigova lema 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. Axiom of Choice Kőnig's Lemma Brooks’ theorem distinguishing proper coloring total coloring list-distinguishing proper coloring Aksiom izbire Kőnigova lema Brooksov izrek razlikovalno pravilno barvanje popolno barvanje seznamsko razlikovalno pravilno barvanje true false true Založba Univerze na Primorskem Angleški jezik Slovenski jezik Članek v reviji 2025-10-22 22:08:45 2025-10-22 22:08:45 2025-11-15 03:02:57 0000-00-00 00:00:00 2025 0 0 24 str. no. 4, [article no.] P4.06 Vol. 25 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2025-08-20 51 1855-3974 https://doi.org/10.26493/1855-3974.3453.4a8 RAZ_Banerjee,Molnar,Gopaulsingh_2025.pdf RAZ_Banerjee,Molnar,Gopaulsingh_2025.pdf 1 D23F5F238E80C3A0B60071887811B248 22fbb0e51f3fe4bd68bdede3b73d644703f1c28774895264394272b49420d00f d3c2aaa1-af83-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=31954 Založba Univerze na Primorskem 0 0 0