Brooks' type theorems for coloring parameters of locally finite graphs and Kőnig's Lemma

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.