## BROOKS' TYPE THEOREMS FOR COLORING PARAMETERS OF LOCALLY FINITE GRAPHS AND K ˝ NIG'S LEMMA O

AMITAYU BANERJEE , ZAL ´ N MOLN ´ R, AND ALEXA GOPAULSINGH ∗ A A

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 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 K˝nig's Lemma (every infinite locally finite connected graph has a ray-a weak form of o 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 o 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 s 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 o ZF . However, the above statement fails in ZF .

## 1. Introduction

In 1941, Brooks [6] proved that for any connected undirected finite graph G with maximum degree ∆( G ), the chromatic number χ G ( ) of G is at most ∆( G ), unless G is a complete graph or an odd cycle. Brooks' theorem for connected infinite graphs was proved in 1976 by Behzad and Radjavi [5]. Since then, several authors have found general upper bounds for various coloring parameters of an infinite graph G (cf. [5, 7, 20, 19, 26, 29]). For the reader's convenience, complete definitions of the parameters for graph coloring are stated in the Appendix, so that the proofs appear earlier.

Fact 1.1. ( ZFC ) If G is a connected infinite graph where ∆( G ) is finite, then the following holds:

- (1) (Behzad and Radjavi; [5, Theorem 3] ) The chromatic number χ G ( ) is at most ∆( G ) .
- (2) (Behzad and Radjavi; [5, Theorem 7] ) The chromatic index χ ′ ( G ) is at most ∆( G ) + 1 .
- (3) (Imrich, Klavˇar, and Trofimov; z [20, Theorem 2.1] ) The distinguishing number D G ( ) is at most ∆( G ) .
- (4) (Broere and Pil´niak; s [7, Theorem 4] ) The distinguishing index D G ′ ( ) is at most ∆( G ) .
- (5) (Imrich, Kalinowski, Pil´niak, and Shekarriz; s [19, Theorem 3] ) The distinguishing chromatic number χ D ( G ) is at most 2∆( G ) -1 .
- (6) (Imrich, Kalinowski, Pil´niak, s and Shekarriz; [19, Theorem 14] ) The distinguishing chromatic index χ ′ D ( G ) is at most ∆( G ) + 2 .
- (7) (Lehner, Pil´niak, and Stawiski; s [26, Theorem 3] ) If ∆( G ) ≥ 3 , then D G ( ) ≤ ∆( G ) -1 .
- (8) (Pil´niak and Stawiski; s [29, Theorem 3] ) If ∆( G ) ≥ 3 , then D G ′ ( ) ≤ ∆( G ) -1 .
- (9) (H¨ uning, Imrich, Kloas, Schreiber, and Tucker; [18, Corollary 2] ) If ∆( G ) = 3 , then D G ( ) ≤ 2 .

The coloring parameters can be drastically influenced by the inclusion or exclusion of AC (cf. [3, 12, 15, 16, 30, 31, 32, 34]). Galvin-Komj´ ath [12] proved that AC is equivalent to the statement 'Every graph has a chromatic number'. In a series of papers, Shelah and Soifer [30, 31, 32] have constructed some graphs whose chromatic number is finite in ZFC and uncountable (if it exists) in some models of ZF (e.g. Solovay's model from [33, Theorem 1]). Herrlich-Tachtsis [15, Proposition 23] proved that no Russell graph has a

2020 Mathematics Subject Classification. Primary 03E25; Secondary 05C63, 05C15, 05C25.

Key words and phrases. Axiom of Choice, K˝nig's Lemma, Brooks' theorem, Distinguishing proper coloring, Total coloring, o List-distinguishing proper coloring.

∗ Corresponding author.

chromatic number in ZF . 1 The above results are the main motivation for us to investigate the status of the results in Fact 1.1 when AC is removed.

- 1.1. Results in ZFC : Analogues to Brooks' theorems for the total chromatic number [28], the total distinguishing number [23, Theorem 2.2], the total distinguishing chromatic number [23, Theorem 4.2], and the odd chromatic number [8, Theorem 4.9] were investigated for finite graphs (cf. Fact 3.1). Ferrara et al. [11] extended the notion of distinguishing proper coloring to a list distinguishing proper coloring and introduced the notion of list distinguishing chromatic number for finite graphs. We prove the following:
- (1) (Theorem 3.3) In ZF , K˝ onig's Lemma implies the statement 'If G is a connected infinite graph where ∆( G ) ≥ 3 is finite, then
- (c) the total chromatic number χ ′′ ( G ) is at most ∆( G ) + 10 26 , and
- (a) the total distinguishing number D ′′ ( G ) is at most /ceilingleft √ ∆( G ) /ceilingright , (b) the odd chromatic number χ o ( G ) is at most 2∆( G ) ,
- (d) the total distinguishing chromatic number χ ′′ D ( G ) is at most ∆( G ) + 10 26 +1 '.

The results mentioned in (1) are new results in ZFC concerning the estimation of the upper bound of the listed coloring parameters for infinite locally finite connected graphs. These results are extensions of the known results from Fact 3.1 to infinite locally finite connected graphs.

- (2) (Theorem 7.4) In ZF , K˝ onig's Lemma implies the statement 'If G is a connected infinite graph where ∆( G ) ≥ 3 is finite, then the list-distinguishing chromatic number χ D L ( G ) is at most 2∆( G ) -1 '.
- Obtaining the upper bounds for the list-distinguishing chromatic number of infinite graphs were not previously investigated in ZFC . Thus, it seems that the result mentioned in (2) is a new result in ZFC concerning the estimation of the upper bound of the list-distinguishing chromatic number for infinite locally finite connected graphs. Inspired by the arguments of Imrich, Kalinowski, Pil´niak, s and Shekarriz [19, Theorem 3], we use the methods in this note and generalize the algorithm of [19, Theorem 3] to prove the statement of (2).
- (3) In Remark 7.3, we show that the inequality ' χ D ( G &lt; χ ) D L ( G )' holds in general for a connected infinite graph G where ∆( G ) ≥ 3 is finite in ZFC . Thus, the result mentioned in the statement of (2) strengthens Fact 1.1(5) (cf. Theorem 7.4). 2

## 1.2. Consistency results in ZF :

- (A) (Theorems 6.1, 6.3, 7.4) There are models of ZF where the statements in Fact 1.1(1)-(9), (1), and (2) fail.
- (B) Stawiski [34] proved that the statement 'Every infinite connected subcubic graph G (i.e. ∆( G ) = 3) has a distinguishing number' fails in some model of ZF if one assumes that the sets of colors can be well-ordered (cf. [34, Lemma 3.3 and section 2]). In Theorem 6.3, we strengthen Stawiski's result. In particular, we show that Stawiski's result holds even if the sets of colors cannot be well-ordered.
- 1.3. New equivalents of K˝nig's Lemma: o Inspired by a combinatorial argument of Herrlich-Tachtsis [15, Proposition 23], the first two authors investigate the role of K˝nig's Lemma in the existence of the total o chromatic number, and some recently studied coloring parameters such as the odd chromatic number [8], the distinguishing chromatic number [19], the distinguishing chromatic index [19], the total distinguishing chromatic number [19], and the neighbor-distinguishing index [17]. The following table summarizes the new results (cf. Theorems 4.1, 5.1) as well as the published results [1, 3, 9, 34] on this topic. 3 In the following table, P lf,c (property X ) denotes 'Every infinite locally finite connected graph has property X '.

1 The reader is referred to Herrlich-Tachtsis [15] for the details concerning Russell graph.

2 The result mentioned in (1) also provides new upper bounds for the corresponding coloring parameters for connected infinite graphs in ZFC . Theorems 3.3, 4.1, 5.1, 6.3, 7.4 are due to the first two authors. Moreover, Theorem 6.1, and Remark 7.3 are due to all the authors.

3 K˝ onig's Lemma has several known graph-theoretic equivalents. Fix any integer m ≥ 4. Delhomm´ e-Morillon [9], Banerjee [1, 2], Banerjee-Moln´ ar-Gopaulsingh [3, Theorems 4.2, 5.1] and Stawiski [34, Theorem 3.8] proved that K˝nig's lemma is o equivalent to the statement 'Every infinite locally finite connected graph has a chromatic number ( resp. a chromatic index, a distinguishing number, a distinguishing index, an irreducible proper coloring, a spanning tree, a spanning m -bush, a maximal independent sets, a minimal edge cover, a maximal matching, a minimal dominating set)'.

| Known equivalents of K˝nig's o lemma                                                                                                                                                                         | New equivalents of K˝nig's o lemma                                                                                                                                                                                                                                           |
|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| P lf,c (distinguishing number) P lf,c (distinguishing index) P lf,c (chromatic number) P lf,c (chromatic index) P lf,c (irreducible proper coloring) P lf,c (spanning tree) P lf,c (maximal independent set) | P lf,c (distinguishing chromatic number) P lf,c (distinguishing chromatic index) P lf,c (total chromatic number) P lf,c (total distinguishing chromatic number) P lf,c (neighbor-distinguishing number) P lf,c (neighbor-distinguishing index) P lf,c (odd chromatic number) |

1.4. Remarks and Questions. In Remark 8.1, we observe that the statements (1)-(6), (9) in Fact 1.1 follow from K˝nig's Lemma in o ZF . We also add some open questions of interest.

## 2. Basics

Definition 2.1. Let X and Y be two sets. We write:

- (1) X /precedesequal Y , if there is an injection f : X → Y .
- (2) X and Y are equipotent if X /precedesequal Y and Y /precedesequal X , i.e., if there is a bijection f : X → Y .
- (3) X ≺ Y , if X /precedesequal Y and X is not equipotent with Y .

Definition 2.2. The von Neumann hierarchy is defined by recursion on the ordinals:

- (1) V 0 = , ∅
- (2) V α +1 = P ( V α ) where P ( X ) is the powerset of a set X ,

The von Neumann universe V is defined as ⋃ α ∈ Ord V α where Ord is the class of all ordinals. The rank of a set x is the least ordinal α such that x ∈ V α +1 (see [21, The paragraph after Lemma 6.3 in Section 6; Pages 64 and 65]). Without AC , a set m is called a cardinal if it is the cardinality | x | of some set x , where | x | = { y : y ∼ x and y is of least rank } where y ∼ x means the existence of a bijection f : y → x (see [24, Definition 2.2, p. 83] and [22, Section 11.2]).

- (3) V α = ⋃ β&lt;α V β if α is a limit ordinal.

Definition 2.3. A topological space ( X,τ ) is called compact if for every U ⊆ τ such that ⋃ U = X there is a finite subset V ⊆ U such that ⋃ V = X .

Definition 2.4. Let ω be the set of all natural numbers. A set X is Dedekind-finite if it satisfies the following equivalent conditions (cf. [15, Definition 1]):

- · ω /precedesequal X ,

/negationslash

- · A ≺ X for every proper subset A of X .

A set X is finite if there exists an n ∈ ω and a bijection f : X → n . Otherwise, X is called infinite . 4

Definition 2.5. For every family B = { B i : i ∈ I } of non-empty sets, B is said to have a partial choice function if B has an infinite subfamily C with a choice function. The following weak choice forms are equivalent to K˝nig's lemma (cf. o [14], [10, the proof of Theorem 4.1(i)]):

- (1) AC ω fin : Any countably infinite family of non-empty finite sets has a choice function.
- (2) PAC ω fin : Any countably infinite family of non-empty finite sets has a partial choice function.
- (3) The union of a countably infinite family of finite sets is countably infinite.
- 3. Known Results and basic results under K˝nig's Lemma o

## 3.1. Known Results.

Fact 3.1. ( ZF ) The following holds:

- (1) (Kalinowski, Pil´niak, and Wo´niak; s z [23, Theorem 2.2] ) If G is a finite connected graph of order n ≥ 3 , then D ′′ ( G ) ≤ /ceilingleft √ ∆( G ) /ceilingright . 4 Clearly, finite sets are Dedekind-finite sets. In ZFC , but not in ZF , Dedekind-finite sets are finite; see [22].

- (2) (Caro, Petruˇ sevski, and Skrekovski; ˇ [8, Theorem 4.9, Corollary 4.10] ) If G is a finite connected graph where ∆( G ) ≥ 1 , then χ o ( G ) ≤ 2∆( G ) unless G is the cycle graph C 5 .
- (3) (Molloy and Reed; [28] ) If G is a finite graph, then χ ′′ ( G ) ≤ ∆( G ) + 10 26 .

/negationslash

From Fact 3.1(2), we can see that for any graph G (connected or disconnected) where ∆( G ) ≥ 3, we have χ o ( G ) ≤ 2∆( G ). Moreover, if ∆( G ) ≤ 2, then χ o ( G ) = 2∆( G ) + 1 if and only if G has C 5 as a connected component, otherwise χ o ( G ) ≤ 2∆( G ).

- (4) (Loeb; [25, Theorem 1] ) Let { X i } i ∈ I be a family of compact spaces that is indexed by a well-orderable set I . If there is a choice function F on the collection { C : C is closed, C = ∅ , C ⊂ X i for some i ∈ I } , then the product space ∏ i ∈ I X i is compact in the product topology.

## 3.2. Basic results under K˝nig's Lemma. o

Observation 3.2. ( ZF ) Every graph G = ( V G , E G ) based on a well-ordered set of vertices has a distinguishing chromatic number, a distinguishing chromatic index, a total chromatic number, a total distinguishing number, a total distinguishing chromatic number, a neighbor-distinguishing number, a neighbordistinguishing index, and an odd chromatic number. Moreover, if G is connected, then it also has a breadth-first search (BFS) spanning tree rooted at v 0 for each v 0 ∈ V G .

Proof. If V G is well-orderable, then E G ⊆ [ V G ] 2 is also well-orderable. We can therefore color each vertex (or each edge) of G with a unique color. We can use transfinite recursion without invoking any form of choice, and modify the BFS -algorithm to find a spanning tree rooted at v 0 . 5 /square

Theorem 3.3. ( ZF + K˝ onig's Lemma) Let G = ( V G , E G ) be a connected infinite graph where ∆( G ) is finite. Then the following holds:

- (1) D ′′ ( G ) ≤ /ceilingleft √ ∆( G ) /ceilingright , (2) χ o ( G ) ≤ 2∆( G ) ,
- (3) χ ′′ ( G ) ≤ ∆( G ) + 10 26 ,
- (4) χ ′′ D ( G ) ≤ ∆( G ) + 10 26 +1 .

Proof. Choose any r ∈ V G . Let N 0 ( r ) = { } r . For each integer n ≥ 1, define N n ( r ) = { v ∈ V G : d G ( r, v ) = n } , where ' d G ( r, v ) = n ' means that there are n edges on the shortest path connecting r and v . Each N n ( r ) is finite since ∆( G ) is finite, and V G = ⋃ n ∈ ω N n ( r ) since G is connected. By K˝ onig's Lemma, which is equivalent to AC ω fin , V G is countably infinite (and thus well-orderable).

$$\text{$s.equivalent to $v_{fn}$, $v_{G}$ is counter} \, \text{$m.us$ was $recoverance}. \\ ( 1 ). \, \text{ Since $G$ is a connected infinite graph, $\Delta(G) \geq 2$.} \, \text{ Let $v_{0} \in V_{G}$ such that $\deg(v_{0}) = \Delta(G)$.} \, \text{ By} \\ \text{Observation 3.2, there is a BFS spanning tree $T$ of $G$ rooted at $v_{0}$ in $ZF$.} \, \text{ Assign the color 0 to $v_{0}$.} \, \text{ By} \\ \text{König's Lemma, there is an infinite ray $p = (v_{i} \, : i \in \omega )$ in $T$ that starts from $v_{0}$. We will construct a total} \\ \text{distinguishing coloring with $[\sqrt{\Delta(G)}]$ colors. For a vertex $v \in V_{G}$, we denote} \\ N ( v ) = N ^ { 1 } ( v ) \quad \text{and} \quad S ( v ) = \{ ( \{ v, u \}, u ) \, \colon \{ v, u \} \in E_{G} \}. \\ \vdots \cdot \quad - \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \end{$\cdot}$$

Pick z ∈ N v ( 0 ) \{ v 1 } (since selecting an element from a set does not involve any form of choice) and assign the color pair (1 , 1) to both ( { v , v 0 1 } , v 1 ) and ( { v , z 0 } , z ). Since deg( v 0 ) = ∆( G ), and the pair (1 1) is , used twice to color the elements of S v ( 0 ), we can color every pair from S v ( 0 ) \ { { ( v , v 0 1 } , v 1 ) , ( { v , z 0 } , z ) } with distinct pairs of colors different from (1 , 1). Following a similar strategy as in [23, Theorem 2.2] due to Kalinowski, Pil´niak, and Wo´niak, we will color s z G such that v 0 will be the only vertex colored with 0, and the pair (1 , 1) appears twice in S v ( 0 ). Hence v 0 will be fixed by every color preserving automorphism, and all vertices in N v ( 0 ) will be fixed, except possibly, v 1 and z . In order to distinguish v 1 and z , we color the elements from

$$\{ ( \{ v _ { 1 }, u \}, u ) \in S ( v _ { 1 } ) \, \colon u \in N ^ { 2 } ( v _ { 0 } ) \} \quad \text{and} \quad \{ ( \{ z, u \}, u ) \in S ( z ) \, \colon \{ z, u \} \in E _ { T }, u \in N ^ { 2 } ( v _ { 0 } ) \}$$

with two distinct sets of color pairs. This is possible since each of these sets contains at most ∆( G ) -1 pairs, while at least ∆( G )-many distinct color pairs are available. Now suppose that for some k ∈ ω , every element from u ∈ ⋃ i ≤ k N i ( v 0 ) are colored such that they are fixed by every color preserving automorphism.

5 It is important to note that the statement 'Any connected graph contains a partial subgraph, which is a tree' is equivalent to AC (see H¨ft-Howard [13]). o

For every u ∈ N k ( v 0 ), color ( { u, z } , z ), where z is a child of u in T , with distinct color pairs except (1 , 1). Hence, all neighbors in N u ( ) ∩ N k +1 ( v 0 ) will be fixed. Therefore, the elements of ⋃ i ≤ k +1 N v i ( 0 ) are also fixed by every color preserving automorphism.

Continuing in this fashion by mathematical induction (and noting that the process will not stop at a finite stage), we end up coloring the vertices and edges of T . Finally, we color the edges in E G \ E T with 0. The color assignment of G , defined above, is total distinguishing.

- (2). By Fact 3.1(2), every finite subgraph of G is (2∆( G )+1)-odd colorable. Endow the set { 1 , ..., 2∆( G )+ 1 } with the discrete topology and T = { 1 , ..., 2∆( G ) + 1 } V G with the product topology. Since V G is wellorderable, { 1 , ..., 2∆( G ) + 1 }× V G is well-orderable. By Fact 3.1(4), T is compact. We can use Fact 3.1(2) and the compactness of T to prove that G is (2∆( G ) + 1)-odd colorable similarly to the proof of the de Bruijn-Erd˝s theorem, without invoking any form of choice. o If G were not 2∆( G )-odd colorable, then there would exist a finite subgraph H of G with χ o ( H ) = 2∆( G ) + 1 ≥ 2∆( H ) + 1.

/negationslash

By the paragraph after Fact 3.1, we have ∆( H ) ≤ 2 and χ o ( H ) = 2∆( H ) +1. Moreover, H would have C 5 as a connected component, and so ∆( H ) = 1. Thus, ∆( H ) = 2 and χ 0 ( H ) = 2∆( G ) +1 = 2∆( H ) +1 = 5. Consequently, ∆( G ) = 2. Since G is connected and C 5 is a connected component of H , there exists a vertex x of C 5 such that the degree of x in G is greater than or equal to 3. Thus, G would have to contain a vertex of degree greater than ∆( G ), which is impossible.

- (3). This follows from Fact 3.1(3), and a straightforward compactness argument as in (2).
- (4). This follows from (3) and the fact that the statement ' χ ′′ D ( G ) is at most χ ′′ ( G ) + 1' holds in ZF since V G is well-orderable (see [19, proof of Theorem 13]). /square
- 4. Total, Neighbor-distinguishing, and distinguishing proper colorings

In this section, we prove the following.

## Theorem 4.1. ( ZF ) The following statements are equivalent:

- (1) K˝ onig's Lemma.
- (2) Every infinite locally finite connected graph has a distinguishing chromatic number.
- (3) Every infinite locally finite connected graph has a distinguishing chromatic index.
- (4) Every infinite locally finite connected graph has a total chromatic number.
- (5) Every infinite locally finite connected graph has a total distinguishing chromatic number.
- (6) Every infinite locally finite connected graph has a neighbor-distinguishing index.

Let G = ( V G , E G ) be an infinite, locally finite, connected graph. Following the arguments in the first paragraph of the proof of Theorem 3.3, V G is well-orderable by K˝nig's Lemma. Thus, (1) implies (2)-(6) o by Observation 3.2. We show that each of the conditions (2)-(6) implies (1). Since AC ω fin is equivalent to its partial version PAC ω fin (cf. Definition 2.5), it suffices to show that each of (2)-(6) implies PAC ω fin . Let A = { A n : n ∈ ω } be a countably infinite set of non-empty finite sets without a partial choice function. Without loss of generality, we assume that A is disjoint. It is enough to show that there exists an infinite locally finite connected graph G such that G does not have the coloring parameters mentioned in (2)-(6).

/negationslash

- 4.1. Construction of the graph. Pick a countably infinite sequence T = { t n : n ∈ ω } disjoint from A = ⋃ i ∈ ω A i . Pick t , t ′ ′′ ∈ ( ⋃ n ∈ ω A n ) ∪ T such that t ′′ = t ′ and consider the following infinite locally finite connected graph G = ( V G , E G ) (see Figure 1):

/negationslash

Figure 1. Graph G , an infinite locally finite connected graph.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00812v3-figure-38906adf-859a-47ad-9c24-407d69d3fb31.jpg)

$$V _ { G } \coloneqq ( \bigcup _ { n \in \omega } A _ { n } ) \cup T \cup \{ t ^ { \prime }, t ^ { \prime \prime } \}, \\ E _ { G } \coloneqq \{ t ^ { \prime \prime }, t ^ { \prime } \} \cup \{ t ^ { \prime }, t _ { 0 } \} \cup \{ \{ t _ { n }, t _ { n + 1 } \} \, \colon n \in \omega \} \cup \{ \{ t _ { n }, x \} \, \colon n \in \omega, x \in A _ { n } \}. \\ \sim \,. \quad \, \dots \, \dots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \end{$$

- 4.2. G has no distinguishing chromatic number. In this subsection, we show that condition (2) implies PAC ω fin . The following two claims were proved in [3].

Claim 4.2. ([3, Claim 4.7]) Any automorphism of G fixes the vertices t , t ′ ′′ , and t m for each non-negative integer m .

Claim 4.3. ([3, Claim 4.8]) Fix p ∈ ω and x ∈ A p . Then Orb Aut G ( ) ( x ) = { g x ( ) : g ∈ Aut G ( ) } = A p .

Claim 4.4. If f : V G → C is a distinguishing proper vertex coloring of G , then the following holds:

/negationslash

- (1) If x, y ∈ A i such that x = y , then f ( x ) = f ( y ) .

/negationslash

- (3) f [ ⋃ n ∈ ω A n ] is infinite.

Proof. (1). This follows by Claim 4.3.

- (4) f [ ⋃ n ∈ ω A n ] is Dedekind-finite. (5) For each natural number m , if c , ..., c 0 m ∈ f [ ⋃ n ∈ ω A n ] , then there is a proper vertex coloring h : ⋃ n ∈ ω A n → f [ ⋃ n ∈ ω A n ] \ { c 0 , ..., c m } such that h x ( ) = f ( x ) whenever f ( x ) = c i . 6
- (2). If M c is infinite, then it will generate a partial choice function for A by (1).
- (3). If f [ ⋃ n ∈ ω A n ] is finite, then ⋃ n ∈ ω A n = ⋃ c ∈ f [ ⋃ n ∈ ω A n ] M c is finite by (2), since the finite union of finite sets is finite in ZF . Thus, we obtain a contradiction.

/negationslash

/negationslash

- (4). We note that ⋃ n ∈ ω A n is Dedekind-finite since A has no partial choice function. For the sake of contradiction, assume that C = { c i : i ∈ ω } is a countably infinite subset of f [ ⋃ n ∈ ω A n ]. Fix a wellordering of A (since A is countable, and hence well-orderable). Define d i to be the unique element of M c i ∩ A n where n is the least element of { m ∈ ω : M c i ∩ A m = ∅} with respect to the well-ordering of A . Such an n exists since c i ∈ f [ ⋃ n&lt;ω A n ] and M c i ∩ A n has a single element by the property mentioned in (1). Then { d i : i ∈ ω } is a countably infinite subset of ⋃ n ∈ ω A n which contradicts the fact that ⋃ n ∈ ω A n is Dedekind-finite.
- (5). Fix some c 0 ∈ f [ ⋃ n ∈ ω A n ]. Then Index M ( c 0 ) = { n ∈ ω : M c 0 ∩ A n = ∅} is finite. By (3), there exists some b 0 ∈ ( f [ ⋃ n ∈ ω A n ] \ ⋃ m Index M ∈ ( c 0 ) f A [ m ]) (see Figure 2).

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00812v3-figure-ecaa185c-0b24-452a-893c-e4a79d575a3e.jpg)

Figure 2. There exists a color b 0 from the set ( f [ ⋃ n ∈ ω A n ] \ ⋃ m Index M ∈ ( c 0 ) f A [ m ]) .

6 The crux of this claim is inspired by the arguments of Herrlich-Tachtsis [15, Proposition 23] where they proved that no Russell graph has a chromatic number in ZF .

Define a vertex coloring g : ⋃ n ∈ ω A n → ( f [ ⋃ n ∈ ω A n ] \{ c 0 } ) as follows:

- (2) For each c ∈ C , the set M c = f -1 ( c ) ∩ ⋃ i ∈ ω A i must be finite.

/negationslash

/negationslash

$$g ( x ) = \begin{cases} f ( x ) & \text{if $f(x)\neq c_{0}$,} \\ b _ { 0 } & \text{otherwise.} \end{cases}$$

Similar to the definition of g , if c 0 , ..., c m ∈ f [ ⋃ n ∈ ω A n ], then one can define a vertex coloring h : ⋃ n ∈ ω A n → ( f [ ⋃ n ∈ ω A n ] \{ c 0 , ..., c m } ) satisfying the properties of the assertion. /square Claim 4.5. G has no distinguishing chromatic number.

Proof. Assume that G has a distinguishing chromatic number (say κ ). Let f : V G → C be a distinguishing proper vertex coloring with | C | = κ . For some c 0 , c 1 , c 2 ∈ f [ ⋃ n ∈ ω A n ], we can define a vertex coloring h : ⋃ n ∈ ω A n → ( f [ ⋃ n ∈ ω A n ] \{ c 0 , c 1 , c 2 } ) as in Claim 4.4(5). Let h t ( ′′ ) = c 0 , h t ( ′ ) = c 1 , h t ( 2 n ) = c 0 , and h t ( 2 n +1 ) = c 1 for all n ∈ ω . By Claim 4.2, h : V G → ( f [ ⋃ n ∈ ω A n ] \{ c 2 } ) is a distinguishing proper vertex coloring of G . Define C 1 = f [ ⋃ n ∈ ω A n ] \{ c 2 } . By Claim 4.4(4), C 1 ≺ f [ ⋃ n ∈ ω A n ] /precedesequal C which contradicts the fact that χ D ( G ) = κ . /square

Thus, condition (2) implies PAC ω fin . This shows that condition (2) in Theorem 4.1 is equivalent to K˝nig's o Lemma.

- 4.3. A Lemma on edge colorings. By Claim 4.2, every automorphism fixes the edges { t ′′ , t ′ } , { t , t ′ 0 } , and { t n , t n +1 } for each n ∈ ω . The following lemma will be applied in subsections 4.4, 4.5, 4.6, and 4.7. Throughout the section, let B = {{ t n , x } : n ∈ ω, x ∈ A n } .

Lemma 4.6. If f is a distinguishing proper edge coloring (resp. neighbor-distinguishing edge coloring, total coloring) of G , then the following holds:

/negationslash

- (1) For each n ∈ ω and x, y ∈ A n such that x = y , f ( { t n , x } ) = f ( { t n , y } ) .

/negationslash

- (2) f B [ ] is an infinite, Dedekind-finite set.

/negationslash

- (3) For each natural number m , if c , ..., c 0 m ∈ f B [ ] , then there is an edge coloring h : B → f B [ ] \ { c 0 , ..., c m } such that h x ( ) = f ( x ) whenever f ( x ) = c i .

Proof. This follows modifying the arguments of Claims 4.3, and 4.4.

/square

- 4.4. G has no distinguishing chromatic index. In this subsection, we show that condition (3) implies PAC ω fin . Assume that the graph G has a distinguishing chromatic index (say κ ), and let f : E G → C be a distinguishing proper edge coloring with | C | = κ . By Lemma 4.6, f B [ ] is an infinite, Dedekind-finite set. Moreover, for some c 0 , c 1 , c 2 ∈ f B [ ], we can define an edge coloring h : B → f B [ ] \{ c , c 0 1 , c 2 } as in Lemma 4.6(3). Define,
- (1) h ( { t ′′ , t ′ } ) = c 0 , h ( { t , t ′ 0 } ) = c 1 ,
- (2) h ( { t 2 n , t 2 n +1 } ) = c 0 and h ( { t 2 n +1 , t 2 n +2 } ) = c 1 for all n ∈ ω .

We obtain a distinguishing proper edge coloring h : E G → f B [ ] \ { c 2 } , with f B [ ] \ { c 2 } ≺ f B [ ] /precedesequal C as f B [ ] is Dedekind-finite, contradicting the fact that χ ′ D ( G ) = κ .

This shows that K˝nig's Lemma is equivalent to condition (3) in Theorem 4.1. o

- 4.5. G has no neighbor-distinguishing index. Here we show that condition (6) implies PAC ω fin . Assume that G has a neighbor-distinguishing index (say κ ), and let f : E G → C be a neighbor-distinguishing edge coloring with | C | = κ . By Lemma 4.6, f B [ ] is an infinite, Dedekind-finite set and for some c , c 0 1 , c 2 , c 3 ∈ f B [ ], we can define an edge coloring h : B → f B [ ] \ { c 0 , c 1 , c 2 , c 3 } as in Lemma 4.6(3). Define,
- (1) h ( { t ′′ , t ′ } ) = c 1 , h ( { t , t ′ 0 } ) = c 2 ,
- (2) h ( { t 3 n , t 3 n +1 } ) = c 0 , h ( { t 3 n +1 , t 3 n +2 } ) = c 1 , and h ( { t 3 n +2 , t 3 n +3 } ) = c 2 for all n ∈ ω .

Then, h : E G → f B [ ] \{ c 3 } is a neighbor-distinguishing edge coloring of G . Finally, f B [ ] \{ c 3 } ≺ f B [ ] /precedesequal C contradicts the fact that κ is the neighbor-distinguishing index of G .

Thus, K˝ onig's Lemma is equivalent to condition (6) in Theorem 4.1.

4.6. G has no total chromatic number. We show that condition (4) implies PAC ω fin . Assume that G has a total chromatic number. Let f : V G ∪ E G → C be a total coloring with | C | = κ , where κ is the total chromatic number of G . By Lemma 4.6, f B [ ] is an infinite, Dedekind-finite set and for some c i ∈ f B [ ] where 0 ≤ i ≤ 5, we can define an edge coloring h : B → f B [ ] \ { c 0 , c 1 , c 2 , c 3 , c 4 , c 5 } as in Lemma 4.6(3). Let,

- (1) h ( { t ′′ , t ′ } ) = c 0 and h ( { t , t ′ 0 } ) = c 1 .
- (2) h ( { t 2 n , t 2 n +1 } ) = c 0 and h ( { t 2 n +1 , t 2 n +2 } ) = c 1 for all n ∈ ω .
- (3) h t ( ′′ ) = c 2 and h t ( ′ ) = c 3 .
- (4) h t ( 2 n ) = c 2 and h t ( 2 n +1 ) = c 3 for all n ∈ ω .

(5) h x ( ) = c 4 for all x ∈ ⋃ i ∈ ω A i . Then, h : V G ∪ E G → f B [ ] \{ c 5 } is a total coloring of G and f B [ ] \ { c 5 } ≺ f B [ ] /precedesequal C contradicts the fact that κ is the total chromatic number of G .

This shows that K˝nig's Lemma is equivalent to condition (4) in Theorem 4.1. o

4.7. G has no total distinguishing chromatic number. Here we show that condition (5) implies PAC ω fin . Assume that G has a total distinguishing chromatic number, and let f : V G ∪ E G → C be a properly total coloring with | C | = κ such that only the trivial automorphism preserves it, where κ is the total distinguishing chromatic number of G . We claim that the coloring h in subsection 4.6 is defined in a way so that only the trivial automorphism preserves h . In particular, by Claim 4.2, the vertices t , t ′ ′′ , and t m are fixed by every automorphism for each non-negative integer m . Since h is a properly total coloring, any neighbor of t m has to be mapped into itself because every edge incident to t m has a distinct color by Lemma 4.6(1). Thus, following the arguments in subsection 4.6, we obtain a contradiction. So K˝ onig's Lemma is equivalent to condition (5) in Theorem 4.1.

This completes the proof of Theorem 4.1.

## 5. Neighborhood distinguishing and Odd vertex colorings

We prove the following.

Theorem 5.1. ( ZF ) The following statements are equivalent:

- (1) K˝ onig's Lemma.
- (2) Every infinite locally finite connected graph has an odd chromatic number.
- (3) Every infinite locally finite connected graph has a neighbor-distinguishing number.

Implications (1) ⇒ (2)-(3) follow from Observation 3.2, and the fact that AC ω fin implies 'Every infinite locally finite connected graph is countably infinite'. In view of the proof of Theorem 4.1, it suffices to show that each of the conditions (2)-(3) implies PAC ω fin . Assume A and T as in the proof of Theorem 4.1. Consider the following infinite locally finite connected graph G 1 = ( V G 1 , E G 1 ) (see Figure 3):

Figure 3. Graph G 1 , an infinite locally finite connected graph.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00812v3-figure-b08da008-9dd7-4c45-b389-be3f78048a09.jpg)

$$V _ { G _ { 1 } } & \coloneqq ( \bigcup _ { n \in \omega } A _ { n } ) \cup T, \\ E _ { G }, & \coloneqq \{ \{ t _ { n }, t _ { n + 1 } \} \, \colon n \in$$

/negationslash

Claim 5.2. If f : V G 1 → C is an odd proper vertex coloring (resp. neighbor-distinguishing vertex coloring) of G 1 , then the following holds:

E G 1 := { { t n , t n +1 } : n ∈ ω } ∪ { { t n , x } : n ∈ ω, x ∈ A n } ∪ { { x, y } : n ∈ ω, x, y ∈ A ,x n = y } .

/negationslash

- (1) f [ ⋃ n ∈ ω A n ] is an infinite, Dedekind-finite set. (2) For each natural number m , if c 0 , ..., c m ∈ f [ ⋃ n ∈ ω A n ] , then there is an odd proper vertex coloring (resp. neighbor-distinguishing vertex coloring) h : ⋃ n ∈ ω A n → f [ ⋃ n ∈ ω A n ] \ { c 0 , ..., c m } such that h x ( ) = f ( x ) whenever f ( x ) = c i .

Proof. This follows modifying the arguments of Claims 4.3, and 4.4 (cf. [3, the proof of Theorem 4.2] as well as [15, the proof of Proposition 23]). /square

- 5.1. G 1 has no odd chromatic number. Assume that G 1 has an odd chromatic number (say κ ), and let f : V G 1 → C be a C -odd proper vertex coloring with | C | = κ . By Claim 5.2(1), f [ ⋃ n ∈ ω A n ] is an infinite, Dedekind-finite set. Consider the vertex coloring h : ⋃ n ∈ ω A n → f [ ⋃ n ∈ ω A n ] \ { c 0 , c 1 , c 2 } for some c , c 0 1 , c 2 ∈ f [ ⋃ n ∈ ω A n ] as in Claim 5.2(2). Let, h t ( 2 n ) = c 0 , and h t ( 2 n +1 ) = c 1 for all n ∈ ω . Then, h : V G 1 → ( f [ ⋃ n ∈ ω A n ] \{ c 2 } ) is a proper vertex coloring of G 1 . The following arguments show that h is an odd proper vertex coloring:
- (1) If t i ∈ T , then pick the color c of an arbitrary vertex of A i , say a i . Since h is a proper vertex coloring, h -1 ( c ) ∩ N t ( i ) = { a i } where N v ( ) = { u ∈ V G 1 : { u, v } ∈ E G 1 } is the open neighborhood of v for any v ∈ V G 1 .

We define C 1 = f [ ⋃ n ∈ ω A n ] \{ c 2 } . Since f [ ⋃ n ∈ ω A n ] is Dedekind-finite, C 1 ≺ f [ ⋃ n ∈ ω A n ] /precedesequal C . This contradicts the fact that κ is the odd chromatic number of G 1 .

- (2) If x ∈ A m for some m ∈ ω , then let c ∈ { c 0 , c 1 } be the color of t m . Clearly, h -1 ( c ) ∩ N x ( ) = { t m } as neither c 0 nor c 1 belongs to h [ ⋃ n ∈ ω A n ] because h is a proper vertex coloring.
- 5.2. G 1 has no neighbor-distinguishing number. Assume that G 1 has a neighbor-distinguishing number (say κ ), and let f : V G 1 → C be a neighbor-distinguishing vertex coloring with | C | = κ . For some c i ∈ f [ ⋃ n ∈ ω A n ] where 0 ≤ i ≤ 3, we pick a vertex coloring h : ⋃ n ∈ ω A n → ( f [ ⋃ n ∈ ω A n ] \{ c 0 , c 1 , c 2 , c 3 } ) as in Claim 5.2(2). Let, h t ( 3 n ) = c 0 , h t ( 3 n +1 ) = c 1 , and h t ( 3 n +2 ) = c 2 , for all n ∈ ω . Then, h : V G 1 → f [ ⋃ n ∈ ω A n ] \{ c 3 } is a neighbor-distinguishing vertex coloring of G 1 . The rest follows by the arguments of subsection 5.1.

## 6. Analogs of Brooks' theorem fail in ZF

We apply the methods of sections 4 and 5 to show that the results in Fact 1.1 and Theorem 3.3 fail in a model of ZF .

## Theorem 6.1. There is a model of ZF where the following statements fail:

- (1) If G is a connected infinite graph where ∆( G ) is finite, then χ G ( ) ≤ ∆( G ) ,
- (2) If G is a connected infinite graph where ∆( G ) is finite, then χ ′ ( G ) ≤ ∆( G ) + 1 ,
- (3) If G is a connected infinite graph where ∆( G ) is finite, then D G ( ) ≤ ∆( G ) ,
- (4) If G is a connected infinite graph where ∆( G ) ≥ 3 is finite, then D G ( ) ≤ ∆( G ) -1 ,
- (5) If G is a connected infinite graph where ∆( G ) ≥ 3 is finite, then D G ′ ( ) ≤ ∆( G ) -1 ,
- (6) If G is a connected infinite graph where ∆( G ) is finite, then χ D ( G ) ≤ 2∆( G ) -1 ,
- (7) If G is a connected infinite graph where ∆( G ) is finite, then χ ′ D ( G ) ≤ ∆( G ) + 2 ,
- (8) If G is a connected infinite graph where ∆( G ) is finite, then χ ′′ ( G ) ≤ ∆( G ) + 10 26 ,
- (9) If G is a connected infinite graph where ∆( G ) is finite, then χ ′′ D ( G ) ≤ ∆( G ) + 10 26 +1 ,
- (11) If G is a connected infinite graph where ∆( G ) is finite, then D ′′ ( G ) ≤ /ceilingleft √ ∆( G ) /ceilingright . Thus, the results in Fact 1.1(1)-(8) fail in the model.
- (10) If G is a connected infinite graph where ∆( G ) is finite, then χ o ( G ) ≤ 2∆( G ) ,

Proof. Fix any n ∈ ω \{ 0 1 , } . The authors of [10] constructed a model of ZF where the statement 'Any countably infinite family of n -element sets has a partial choice function', i.e. Form 373( n ) in [14], fails (see the paragraph after [10, Corollary 3.2]). In particular, Form 373( n ) fails in the model N 2 ( n ) of [14] (a model of ZFA i.e., Zermelo-Fraenkel set theory with the Axiom of Extensionality weakened to allow

the existence of atoms) (see [14]). Since φ = ' ¬ Form 373( n )' is a boundable statement, there is a model M ( n ) of ZF where φ holds. 7

/negationslash

Let A = { A i : i ∈ ω } be a countably infinite family of n -element sets without a partial choice function in M ( n ). Consider the graphs G and G 1 from the proof of Theorems 4.1 and 5.1 (see Figures 1 and 3). Clearly, ∆( G ) = ∆( G 1 ) = n + 2 ≥ 4. By the arguments in the proof of Theorems 4.1 and 5.1, χ D ( G ), χ ′ D ( G ), χ ′′ ( G ), χ ′′ D ( G ), and χ o ( G 1 ) do not exist. Let H 1 be the graph obtained from the graph G 1 of Figure 3 after deleting the edge set {{ x, y } : m ∈ ω, x, y ∈ A ,x m = y } (see Figure 4). Clearly, H 1 is a connected infinite graph where ∆( H 1 ) = n +2.

Figure 4. Graph H 1 , a connected infinite graph where ∆( H 1 ) = n +2 ≥ 4 .

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00812v3-figure-2ac282d5-9d26-4fb3-92cb-8e6b1dc77b29.jpg)

By the arguments in the proof of [3, Claims 4.5, 4.6, 4.9, 4.10] figured out by the authors, χ G ( 1 ), χ ′ ( H ,D G , 1 ) ( ) and D G ′ ( ) do not exist. Thus, (1)-(10) fails in M ( n ).

Claim 6.2. Let f : G → D ′′ ( G ) be a total distinguishing coloring of G , and B = ( { { t n , x } , x ) : n ∈ ω, x ∈ A n } . Let g : B → D ′′ ( G ) × D ′′ ( G ) be the function that maps ( { t, x } , x ) to ( f ( { t, x } ) , f ( x )) . Then the following holds:

/negationslash

- (1) For each natural number n and for each x, y ∈ A n such that x = y , we have g ( { t n , x } , x ) = g ( { t n , y } , y ) (i.e., { f ( { t n , x } ) , f ( x ) } /negationslash = { f ( { t n , y } ) , f ( y ) } ).

/negationslash

- (2) g B [ ] is an infinite set.

Proof. (1) is straightforward. Define, N ( c 1 ,c 2 ) = { { ( t n , x } , x ) ∈ g -1 ( c 1 , c 2 ) : n ∈ ω, x ∈ A n } for ( c 1 , c 2 ) ∈ g B [ ]. Clearly, N ( c 1 ,c 2 ) is finite; otherwise, π 2 [ N ( c 1 ,c 2 ) ] will generate a partial choice function of A by (1), where π 2 is the function that maps ( { t n , x } , x ) to x . Now, B = ⋃ ( c 1 ,c 2 ) ∈ g B [ ] N ( c 1 ,c 2 ) . If g B [ ] is finite, then B is finite, which is a contradiction. Thus g B [ ] is infinite. /square

We claim that D ′′ ( G ) is infinite (if it exists), and so (11) fails in M × ( n ). If D ′′ ( G ) is finite, then D ′′ ( G ) × D ′′ ( G ) is finite. This contradicts Claim 6.2(2), since g B [ ] ⊆ D ′′ ( G ) D ′′ ( G ). /square

Theorem 6.3. There is a model of ZF where the statements 'If G is a connected infinite graph where ∆( G ) = 3 , then D G ( ) ≤ 2 ' and 'Any connected infinite graph G where ∆( G ) = 3 , has a distinguishing number' fail. Thus, the result in Fact 1.1(9) fails in the model.

Proof. Fix n = 2, and assume the model M (2) as in the proof of Theorem 6.1 where A = { A i : i ∈ ω } is a countably infinite family of n -element sets without a partial choice function. Pick two disjoint countably infinite sequences T = { t n : n ∈ ω } , and R = { r n : n ∈ ω } which are also disjoint from A = ⋃ i ∈ ω A i . Consider the following graph G 2 = ( V G 2 , E G 2 ) where ∆( G 2 ) = 3 (see Figure 5):

$$V _ { G _ { 2 } } & \coloneqq ( \bigcup _ { n \in \omega } A _ { n } ) \cup T \cup R, \\ E _ { G } & \coloneqq \{ \{ r _ { n }, r _ { n + 1 } \} \colon n \in \omega \} \cup \{ \{ r _ { n }, t _ { n } \} \colon n \in \omega \} \cup \{ \{ t _ { n }, x \} \colon n \in \omega, x \in A _ { n } \}. \\ \intertext { r - 1 \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \end{r}$$

$$\cdot$$

We show that G 2 has no distinguishing number in M (2). Stawiski [34, Claim 1] proved that each x ∈ V G 2 \ ( ⋃ n ∈ ω A n ) is fixed by any automorphism of G 2 and for every i ∈ ω and x ∈ A i , Orb Aut G ( 2 ) ( x ) = { g x ( ) : g ∈ Aut G ( 2 ) } = A i . Assume that D G ( 2 ) exists. Let f : V G 2 → C be a distinguishing vertex

7 We refer the reader to [14, Note 103, pages 283-286] for the definition of the term 'boundable statement' and the fact that a boundable sentence is transferable to ZF .

Figure 5. Graph G 2 , a connected infinite graph where ∆( G 2 ) = 3 . In particular, the degree of t i and r i +1 is 3 for each i ∈ ω , while the degree of r 0 is 2 and the degree of x is 1 for each x ∈ A .

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00812v3-figure-4dcd09fd-e9b9-4edc-8ef1-45512c849381.jpg)

coloring with | C | = D G ( 2 ). Similar to Claim 4.4, f [ ⋃ n ∈ ω A n ] is infinite and Dedekind-finite. Consider a coloring h : ⋃ n ∈ ω A n → f [ ⋃ n ∈ ω A n ] \ { c 0 , c 1 } for some c 0 , c 1 ∈ f [ ⋃ n ∈ ω A n ], as in Claim 4.4. Let, h t ( ) = c 0 for all t ∈ R ∪ T . Then, h : V G 2 → ( f [ ⋃ n ∈ ω A n ] \{ c 1 } ) is a distinguishing vertex coloring of G 2 and f [ ⋃ n ∈ ω A n ] \ { c 1 } ≺ f [ ⋃ n ∈ ω A n ] /precedesequal C contradicts the fact that | C | = D G ( 2 ). /square

## 7. List-distinguishing chromatic numbers for infinite graphs

Definition 7.1. Let T be a tree rooted at v . The parent of z is the vertex immediately following z on the unique path from z to the root v . Two vertices are siblings if they have the same parent.

Definition 7.2. Given an assignment L = L v ( ) v ∈ V G of lists of available colors to the vertices of G , we say that G is properly L-distinguishable if there is a distinguishing proper vertex coloring f of G such that f ( v ) ∈ L v ( ) for all v ∈ V G . The list-distinguishing chromatic number of G , denoted by χ D L ( G ), is the least cardinal κ (if it exists) such that G is properly L -distinguishable for any list assignment L with | L v ( ) | = κ for all v ∈ V G (cf. [11]).

/negationslash

Remark 7.3. Since all lists can be identical, χ D ( G ) ≤ χ D L ( G ) for any graph G in ZFC . We construct a connected infinite graph H where χ D L ( H ) = χ D ( H ), and ∆( H ) = 5. Consider the graph H given in Figure 6. Since H is bipartite and has no non-trivial automorphisms, we have that χ D ( H ) = χ H ( ) = 2.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00812v3-figure-8ea2b7a6-85a8-4b91-8e16-1cd5a2367a64.jpg)

/negationslash

Figure 6. A connected infinite graph H where ∆( H ) = 5 and χ D L ( H ) = χ D ( H ) = 2 .

/negationslash

Consider the following assignment of lists: L v ( 0 ) = { 1 2 , } , L v ( 1 ) = { 1 3 , } , L v ( 2 ) = { 2 3 , } , L v ( 3 ) = { 1 4 , } , L v ( 4 ) = { 2 4 , } , L v ( 5 ) = { 3 4 , } , and for 0 ≤ i ≤ ω , L s ( i ) = { 5 6 , } . Then there is no proper coloring of H from { L v ( ) } v ∈ V H , since { v , . . . , v 0 5 } do not have a proper coloring from the given lists. Thus, χ D L ( H ) = 2.

Theorem 7.4. There is a model of ZF where the statement 'If G is a connected infinite graph where ∆( G ) ≥ 3 is finite, then the list-distinguishing chromatic number χ D L ( G ) is at most 2∆( G ) -1 ' fails. Moreover, the statement holds under K˝nig's Lemma in o ZF .

Proof. Let A = { A n : n ∈ ω } be a countably infinite family of 2-element sets without a partial choice function in the model M (2) of ZF constructed in the proof of Theorem 6.1. Consider the graph G from the proof of Theorem 4.1, where ∆( G ) = 4. We show that χ D L ( G ) cannot be finite (if it exists) in M (2). Assume that χ D L ( G ) exists. Let L = L v ( ) v ∈ V G be an assignment of identical lists of available colors to the vertices of G such that | L v ( ) | = χ D L ( G ). Then there is a distinguishing proper vertex coloring f of G such that f ( v ) ∈ L v ( ) for all v ∈ V G . By the methods of Claim 4.4(3), f [ ⋃ n ∈ ω A n ] is infinite. Hence, χ D L ( G ) cannot be finite and the statement in the assertion fails.

We show that the statement holds under K˝nig's Lemma. o Since G is locally finite and connected, V G is countably infinite (and hence well-orderable). Let L = { L v ( ) } v ∈ V G be an assignment of lists with | L z ( ) | = 2∆( G ) -1, for all z ∈ V G . By K˝ onig's Lemma, ⋃ z ∈ V G L z ( ) is countably infinite (and hence wellorderable) (cf. Definition 2.5). Let v ∈ V G be a vertex with degree ∆( G ). By Observation 3.2, without invoking any form of choice, let T be a BFS spanning tree of G rooted at v . Let,

- · &lt; denote the BFS order of T ,
- · &lt; ′ be a well-ordering of ⋃ z ∈ V G L z ( ), and · &lt; ′′ be a well-ordering of V G .

For z ∈ V G , N z ( ) denotes the set of its neighbors in G , and S z ( ) denotes the set of its siblings in T . The claim below holds in ZF .

Claim 7.5. There are partial functions f x : V G → ⋃ z ∈ V G L z ( ) for each x ∈ V G so that the following holds: (i) if x &lt; y , then f x ⊆ f y ,

- (ii) the domain of f x , i.e., dom f ( x ) , includes all vertices till x in the BFS order.
- (iii) if f = ⋃ x ∈ V G f x , then f ( w ) ∈ L w ( ) for all w ∈ V G and f is a proper vertex coloring of G . (iv) With respect to the coloring f mentioned in (iii), each vertex is colored differently from its siblings and from its parent in the BFS spanning tree T .

Proof. Let, c v = min &lt; ′ ( L v ( )). If { v , . . . , v 1 ∆( G ) } are the neighbors of v arranged in the BFS order &lt; , then let c v i = min &lt; ′ ( L v ( i ) \{ c v j : 1 ≤ j &lt; i } ) where 1 ≤ i ≤ ∆( G ). Let f v = { ( v, c v ) } , f v 1 = f v ∪ { ( v , c 1 v 1 ) } , and f v i = f v i -1 ∪{ ( v , c i v i ) } for each 2 ≤ i ≤ ∆( G ). We proceed inductively in the BFS order &lt; as follows: Let x ∈ V G be the &lt; -minimal element for which no color has been assigned and z &lt; x be the immediate BFS predecessor of x . We define f x . Let us write,

$$S _ { < } ( x ) = \{ y \in S ( x ) \, \colon y < x \} \text{ and } N _ { < } ( x ) = \{ y \in N ( x ) \, \colon y < x \}.$$

Then f z has already assigned colors to each member of S &lt; ( x ) ∪ N &lt; ( x ). Define,

$$\begin{array} { c } \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \colon \\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \ddots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\ A _ { x } = L ( x ) \, \sum \left ( \{ c _ { v } \, \} \cup f _ { z } [ S _ { < } ( x ) ] \, \cup f _ { z } [ N _ { < } ( x ) ] \right ). \end{array}$$

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00812v3-figure-a41aecf4-4118-4ae8-994e-a6a625c8d0e4.jpg)

/negationslash

Figure 7. Defining f x when A x = ∅ .

/negationslash

If A x = ∅ , then let f x = f z ∪ { ( x, c ) } , where c = min &lt; ′ ( A x ) (see Figure 7). If A x = ∅ , then since | N x ( ) | ≤ ∆( G ) and | S x ( ) | ≤ ∆( G ) -2, we must have used | S &lt; ( x ) | + | N &lt; ( x ) | = 2∆( G ) -2 many colors from L x ( ) to color the neighbors and siblings that come before x . Thus, the following holds:

- ( a ) c v ∈ L x ( ),
- ( b ) S &lt; ( x ) = S x ( ) and N &lt; ( x ) = N x ( ),
- ( c ) | S x ( ) | = ∆( G ) -2 and | N x ( ) | = ∆( G ),
- ( d ) N x ( ) ∩ S x ( ) = ∅ ,
- ( e ) for all y ∈ S x ( ) ∪ N x ( ), we have f z ( y ) ∈ L x ( ).

/negationslash

In this case, let f x = f z ∪ { ( x, c v ) } . In either case, f x has (i) and (ii). Finally, set f = ⋃ x ∈ V G f x . Clearly, f satisfies (iii) and (iv), and if f ( x ) = c v where x = v , then ( a ) -( e ) must hold. /square

Let c v 1 , . . . , c v ∆( G ) be as in the proof of Claim 7.5. For any x ∈ V G , we say x has property ( ∗ ) if the following holds:

x is colored by c v , while all its neighbors are colored by c v 1 , . . . , c v ∆( G ) .

Generalizing the algorithm of Imrich, Kalinowski, Pil´niak, and Shekarriz [19, Theorem 3] in the context s of list coloring as well as in ZF , we try to keep v as the only vertex of G with property ( ∗ ) (cf. [4, Theorem 3.1] for finite graphs). Then f is a proper distinguishing coloring. However, suppose there is a vertex other than v , say x , with the property ( ∗ ) and is the &lt; -minimal such vertex. Then ( a ) -( e ) in Claim 7.5 are satisfied for x . We modify f so that x no longer has the property ( ∗ ), while it remains a proper coloring, by analyzing the following cases: 8

/negationslash

Case 1: There is w ∈ S x ( ) such that | N w ( ) | = | N x ( ) | (and let w be the &lt; ′′ -minimal such element). We color x with f ( w ), which can be done by ( e ). Then there is no color-preserving automorphism of G , which fixes v and maps x to w . By ( d ), the new coloring is proper. Moreover, x no longer has the property ( ∗ ).

/negationslash

/negationslash

Case 2: For every z ∈ S x ( ), we have | N z ( ) | = | N x ( ) , | and there is a w ∈ S x ( ) such that N w ( ) = N x ( ) (and let w be the &lt; ′′ -minimal such element). By ( ), we have c N x ( ) \ N w ( ) = ∅ . Fix y ∈ N x ( ) \ N w ( ). By ( e ), we have f ( w , f ) ( y ) ∈ L x ( ) . We color x with f ( w ). The rest follows the arguments in Case 1 .

Case 3: For every w ∈ S x ( ), we have N w ( ) = N x ( ).

Subcase 3.1: There is a vertex z ∈ N x ( ) with no sibling or parent colored with c v (and let z be the &lt; ′′ -minimal such element). We need to consider two different cases.

/negationslash

/negationslash

Case A: If c v ∈ L z ( ), then by ( ) at most (∆( c G ) -1) + (∆( G ) -2) = 2∆( G ) -3 number of colors can appear in the list L z ( ) that are used for coloring N z ( ) ∪ S z ( ). Hence, there exists c ∈ L z ( ) such that c = f ( z ), which also differs from all the colors assigned to N z ( ) ∪ S z ( ). Assume c is the &lt; ′ -minimal such element of L z ( ). We color z with c and x with f ( z ). Then x no longer has the property ( ∗ ) as no member of N v ( ) has color c , and this modification keeps the coloring proper.

/negationslash

/negationslash

Moreover, z does not have the property ( ∗ ) as z is colored by c but c = c v since c ∈ L z ( ) and c v ∈ L z ( ).

Case B: If c v ∈ L z ( ), then color x with f ( z ) and z with c v , which can be done by ( ). e This modification keeps the coloring proper and x does not have the property ( ∗ ).

We show that z does not have the property ( ∗ ). For the sake of contradiction, assume that z has the property ( ∗ ). We show that there exists w ∈ N z ( ) such that w is not colored by any of c v 1 , ..., c v ∆( G ) to obtain a contradiction. Since ∆( G ) ≥ 3, we have | S x ( ) | = ∆( G ) -2 ≥ 1. Pick any w ∈ S x ( ). Since x had the property ( ∗ ) initially, the members of N x ( ) were colored by the colors of { c v 1 , ..., c v ∆( G ) } . After recoloring, the members of N x ( ) were colored by the colors of the set C z ( ) = ( { c v 1 , ..., c v ∆( G ) }∪{ c v } \{ ) f ( z ) } where f ( z ) ∈ { c v 1 , ..., c v ∆( G ) } . Since w is adjacent to all members of N x ( ), w is not colored with the colors of C z ( ) since the modified coloring is proper. Moreover, w is not colored by f ( z ). Otherwise, z has two neighbors w and x with the same color f ( z ) which implies that z does not have ( ∗ ), and we obtain a contradiction. Thus, w is not colored by any of c v 1 , ..., c v ∆( G ) .

Subcase 3.2: Each y ∈ N x ( ) has a sibling or parent colored with c v . By ( ), each b y ∈ N x ( ) and its siblings must have come before x in the BFS ordering &lt; . Hence, their parent cannot have the property ( ∗ ), unless it is the root v (since x is assumed to be the &lt; -minimal vertex with the property ( ∗ )).

Figure 8. In Subcase 3.2, N w ( ) = N x ( ) for every w ∈ S x ( ) , and z ∈ N x ( ) has a sibling or parent colored with c v . Moreover, | N x ( ) | = ∆( G ) and S x ( ) = ∆( G ) -2 .

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00812v3-figure-361a317a-da37-4a84-9616-cebb2599a93b.jpg)

Claim 7.6. There exists a z ∈ N x ( ) such that z is not a child of v .

8 We note that Case 1 and Case A of Subcase 3.1 arise when the lists are nonidentical. Hence, they didn't appear in the algorithm of Imrich, Kalinowski, Pil´niak and Shekarriz [19, Theorem 3]. s Subcase 3.2 is also slightly different in our case.

Proof. Otherwise, z is a child of v for all z ∈ N x ( ). We recall the following:

- · | S x ( ) | = ∆( G ) -2 and | N x ( ) | = ∆( G ) (see ( c )).
- · For every w ∈ S x ( ), we assumed that N w ( ) = N x ( ) in Case 3. Thus, | N w ( ) | = ∆( G ).
- · For every z ∈ N x ( ), z is a child of v and so N z ( ) = { x } ∪ { v } ∪ S x ( ) and | N z ( ) | = ∆( G ).

Consequently, G is isomorphic to a complete bipartite graph K ∆( G , ) ∆( G ) where the bipartitions are N x ( ) and { x } ∪ { v } ∪ S x ( ). Since ∆( G ) is assumed to be finite, this contradicts the assumption that G is infinite. /square

Without loss of generality, let z be the &lt; ′′ -minimal such element. Let B z ( ) denotes the set of colors assigned to the vertices of N z ( ) ∪ S z ( ).

## Claim 7.7. The set L z ′ ( ) = L z ( ) \{ f ( z ) ∪ B z ( ) } is non-empty.

Proof. Let p be the parent of z in T . Then N z ( ) = S x ( ) ∪ { p } ∪ { x } , | S z ( ) | ≤ ∆( G ) -2, and | N z ( ) | = | S x ( ) ∪ { p } ∪ { x }| = ∆( G ). The color c v was used once for x and once among the vertices of S z ( ) ∪ { p } . Thus, | B z ( ) | ≤ 2∆( G ) -3. Since | L z ( ) | = 2∆( G ) -1, the rest follows. /square

/negationslash

Define c = min &lt; ′ ( L z ′ ( )). Using ( ), we can color e x with f ( z ) and z with c (see Figure 8). We note that z does not get property ( ∗ ). This is because c = c v since c v ∈ B z ( ). Similarly, as in the previous cases, the new coloring remains a proper coloring, and v is the only &lt; -predecessor of x having the property ( ∗ ), and all of them are fixed as long as v is fixed.

By iterating this procedure at most countably-infinitely many times (since V G is countably infinite), we can recolor every vertex with the property ( ∗ ) and obtain a distinguishing proper coloring g of G such that g v ( ) ∈ L v ( ) for all v ∈ V G . Hence, G is properly L -distinguishable. /square

## 8. Remarks and Questions

Remark 8.1. The results mentioned in Fact 1.1((1)-(6) and (9)) follow from K˝ onig's Lemma in ZF . Following the arguments of Theorem 3.3(2) and [5, Theorems 3,7], the statements (1) and (2) in Fact 1.1 hold in ZF if the vertex set V G of G is countably infinite. One may modify the algorithms mentioned in the references in Fact 1.1((3)-(6) and (9)) to see that those results hold in ZF + K˝ onig's Lemma, if V G is countably infinite. The rest follows from the fact that any locally finite, connected graph is countably infinite under K˝nig's Lemma. o

Question 8.2. Are the following statements equivalent to AC (without assuming that the sets of colors can be well-ordered)?

- (1) Every connected infinite graph has a chromatic index.
- (2) Every connected infinite graph has a distinguishing number.
- (3) Every connected infinite graph has a distinguishing index.
- (4) Every connected infinite graph has a distinguishing chromatic number.
- (5) Every connected infinite graph has a distinguishing chromatic index.
- (6) Every connected infinite graph has a total chromatic number.
- (7) Every connected infinite graph has a total distinguishing chromatic number.
- (8) Every connected infinite graph has a neighbor-distinguishing number.
- (9) Every connected infinite graph has a neighbor-distinguishing index.

## 9. Appendix

In this section, we list the complete definitions of the graph coloring parameters.

Definition 9.1. A graph G = ( V G , E G ) consists of a set V G of vertices and a set E G ⊆ [ V G ] 2 of edges (i.e., E G is a subset of the set of all two-element subsets of V G ). The degree of a vertex v ∈ V G , denoted by deg v ( ), is the number of edges emerging from v . We denote by ∆( G ) the maximum degree of G . Fix n ∈ ω . A path of length n is a one-to-one finite sequence { x i } 0 ≤ ≤ i n of vertices such that for each i &lt; n , { x , x i i +1 } ∈ E G ; such a path joins x 0 to x n . A ray is an infinite graph with vertex set V = { v , v 1 2 , ... } such

that there is an edge between v i and v i +1 for each natural number i . The graph G is locally finite if every vertex of G has a finite degree and it is connected if any two vertices are joined by a path of finite length. K˝ onig's Lemma states that every infinite locally finite connected graph has a ray. The cycle graph on n vertices for any natural number n ≥ 3, is denoted by C n . A tree is a connected graph with no cycles, and a spanning tree T of G is a subgraph that is a tree and contains all the vertices of G . The automorphism group of G , denoted by Aut G ( ), is the group consisting of automorphisms of G with composition as the operation. Let τ be a group acting on a set S and let a ∈ S . The orbit of a , denoted by Orb τ ( a ), is the set { φ a ( ) : φ ∈ τ } . Two vertices x, y ∈ V G are adjacent vertices if { x, y } ∈ E G , and two edges e, f ∈ E G are adjacent edges if they share a common vertex.

/negationslash

- (1) A proper vertex coloring of G with a color set C is a mapping f : V G → C such that for every { x, y } ∈ E G , f ( x ) = f ( y ).

/negationslash

- (2) A proper edge coloring of G with a color set C is a mapping f : E G → C such that for any two adjacent edges e 1 and e 2 , f ( e 1 ) = f ( e 2 ).

/negationslash

- (3) A total coloring of G with a color set C is a mapping f : V G ∪ E G → C such that for every { x, y } ∈ E G , f ( x , f ) ( { x, y } ) and f ( y ) are all different and for any two adjacent edges e 1 and e 2 , f ( e 1 ) = f ( e 2 ).
- (4) An odd proper vertex coloring of G is a proper vertex coloring f such that for each non-isolated vertex x ∈ V G , there exists a color c such that | f -1 ( c ) ∩ N x ( ) | is an odd integer where N v ( ) = { u ∈ V G : { u, v } ∈ E G } is the open neighborhood of v for any v ∈ V G (cf. [8, Introduction]).
- (5) An automorphism of G is a bijection φ : V G → V G such that { u, v } ∈ E G if and only if { φ u , φ v ( ) ( ) } ∈ E G . Let f be an assignment of colors to either vertices or edges of G . We say that an automorphism φ of G preserves f if each vertex (edge) of G is mapped to a vertex (edge) of the same color. We say that f is a distinguishing coloring if the only automorphism that preserves f is the identity and f is a distinguishing proper vertex coloring if f is a distinguishing coloring as well as a proper vertex coloring. Similarly, we can define a distinguishing proper edge coloring (cf. [19, Introduction]).
- (6) A total distinguishing coloring of G with a color set C is a mapping g : V G ∪ E G → C such that g is only preserved by the trivial automorphism. Moreover, g is a properly total distinguishing coloring if g is total distinguishing and it is a total coloring (see [23]).
- (7) Let | C | = κ . We say G is κ -proper vertex colorable ( κ -odd proper vertex colorable, κ -total colorable, κ -proper edge colorable, κ -distinguishing vertex colorable, κ -distinguishing proper vertex colorable, κ -distinguishing edge colorable, κ -distinguishing proper edge colorable, κ -distinguishing total colorable, κ -properly distinguishing total colorable) if there is a proper vertex coloring (odd proper vertex coloring, total coloring, proper edge coloring, distinguishing vertex coloring, distinguishing proper vertex coloring, distinguishing edge coloring, distinguishing proper edge coloring, total distinguishing coloring, properly total distinguishing coloring) f with a color set C .
- (8) The least cardinal κ for which G is κ -proper vertex colorable ( κ -total colorable, κ -odd proper vertex colorable, κ -proper edge colorable, κ -distinguishing vertex colorable, κ -distinguishing proper vertex colorable, κ -distinguishing edge colorable, κ -distinguishing proper edge colorable, κ -distinguishing total colorable, κ -properly distinguishing total colorable) if it exists, is the chromatic number ( χ G ( )) ( total chromatic number ( χ ′′ ( G )) , odd chromatic number ( χ o ( G )) , chromatic index ( χ ′ ( G )) , distinguishing number ( D G ( )) , distinguishing chromatic number ( χ D ( G )) , distinguishing index ( D G ′ ( )) , distinguishing chromatic index ( χ ′ D ( G )) , total distinguishing number ( D ′′ ( G )) , total distinguishing chromatic number ( χ ′′ D ( G ))) of G .

/negationslash

/negationslash

- (9) For a κ -proper edge coloring f of G C , f ( v ) denotes the set of colors assigned to the edges incident with a vertex v . The coloring f is called κ -neighbor-distinguishing proper edge coloring if C f ( u ) = C f ( v ) for any { u, v } ∈ E G (cf. [17, Introduction]). For a κ -proper vertex coloring f of G N , f ( v ) denotes the set of colors of the neighbors of v . The κ -proper vertex coloring f is called neighbordistinguishing if N f ( u ) = N f ( v ) for any { u, v } ∈ E G . The neighbor-distinguishing index ( χ ′ N ( G )) ( neighbor-distinguishing number ( χ N ( G ))) of G is the least cardinal κ (if it exists) such that G has a κ -neighbor-distinguishing proper edge coloring ( κ -neighbor-distinguishing proper vertex coloring).

## 10. Acknowledgement

The authors are very thankful to the three anonymous referees for reading the manuscript in detail and for providing several comments and suggestions that improved the quality of the paper.

## References

- [1] Banerjee, A.: Maximal independent sets, variants of chain/antichain principle and cofinal subsets without AC , Comment. Math. Univ. Carolin. 64 , 137-159 (2023). doi: https://doi.org/10.14712/1213-7243.2023.028
- [2] Banerjee, A.: Partition models, Permutations of infinite sets without fixed points, and weak forms of AC , Comment. Math. Univ. Carolin. to appear. arXiv: 2109.05914v4 [math.LO]
- [3] Banerjee, A., Moln´r, Z., Gopaulsingh, A.: a Distinguishing colorings, proper colorings, and covering properties without AC , Ars Math. Contemp. 24 (2024). doi: https://doi.org/10.26493/1855-3974.3233.185
- [4] Banerjee, A., Moln´r, Z., Gopaulsingh, A.: Upper bounds for the list-distinguishing chromatic number, Submitted, arXiv: a 2405.12733v2 [math.CO]
- [5] Behzad, M., Radjavi, H.: Chromatic Numbers of Infinite Graphs, J. Comb. Theory Series B 21 , 195-200 (1976). doi: https://doi.org/10.1016/S0095-8956(76)80002-0
- [6] Brooks, R.L.: On colouring the nodes of a network, Math. Proc. Cambridge Philos. Soc. 37 , 194-197 (1941). doi: https://doi.org/10.1017/S030500410002168X
- [7] Broere, I., Pil´niak, M.: s The distinguishing index of the infinite graphs, Electron. J. Combin. 22 (2015), #P1.78. doi: https://doi.org/10.37236/3933
- [8] Caro, Y., Petruˇevski, M, ˇ krekovski. R.: Remarks on odd colorings of graphs, Discrete Appl. Math. s S 321 , 392-401 (2022). doi: https://doi.org/10.1016/j.dam.2022.07.024
- [9] Delhomm´ e, C., Morillon, M.: Spanning Graphs and the Axiom of Choice, Rep. Math. Logic 40 , 165-180 (2006).
- [10] De la Cruz, O., Hall, E.J., Howard, P., Keremedis, K, Rubin, J.E.: Unions and the axiom of choice, Math. Log. Quart. 54 , 652-665 (2008). doi: https://doi.org/10.1002/malq.200710073

[11]

Ferrara, M., Gethner, E., Hartke, S.G., Stolee, D., Wenger, P. S., List distinguishing parameters of trees,

Discrete Appl.

Math.

161

,

864-869 (2013). doi:

https://doi.org/10.1016/j.dam.2012.10.003

- [12] Galvin, F, Komj´ ath, P.: Graph colorings and the axiom of choice, Period. Math. Hungar. 22 , 71-75 (1991). doi: https://doi.org/10.1007/BF02309111
- [13] H¨ oft, H., Howard, P.: A graph theoretic equivalent to the axiom of choice, Math. Log. Quart. 19 , 191-191 (1973). doi: https://doi.org/10.1002/malq.19730191103
- [14] Howard, P., Rubin, J.E.: Consequences of the Axiom of Choice, volume 59 of Mathematical Surveys and Monographs, American Mathematical Society, Providence, RI, 1998. doi: http://dx.doi.org/10.1090/surv/059

[15]

Herrlich, H., Tachtsis,

E.:

On the number of Russell's socks or 2+2+2+

·

·

·

=?, Comment. Math. Univ. Carolin.

47

,

707-717 (2006).

http://dml.cz/dmlcz/119630

- [16] Herrlich, H., Rhineghost, Y.T.: Graph-Coloring and Choice a Note on a Note by Shelah and Soifer, Quaest. Math. 28 , 317-319 (2005). doi: https://doi.org/10.2989/16073600509486131

[17]

Huang. D., Cai, H., Wang, W., Huo, J.:

Neighbor-distinguishing indices of planar graphs with maximum degree ten,

Discrete Appl. Math.

329

,

49-60 (2023). doi:

https://doi.org/10.1016/j.dam.2022.12.023

- [18] H¨ uning, S., Imrich, W., Kloas, J., Schreber, H., Tucker, T.W.: Distinguishing graphs of maximum valence 3, Electron. J. Combin. 26 (2019), #P4.36. doi: https://doi.org/10.37236/7281

[19]

Imrich,

W.,

Kalinowski,

R.,

Pil´niak,

s

M.,

Shekarriz,

M.H.:

Bounds for distinguishing

invariants of

infinite graphs,

Electron. J. Combin.

24

(2017), #P3.6. doi:

https://doi.org/10.37236/6362

- [20] Imrich, W., Klavˇ zar, S., Trofimov, V.: Distinguishing Infinite Graphs, Electron. J. Combin. 14 (2007), #R36. doi: https://doi.org/10.37236/954
- [21] Jech, T.: Set theory, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003, The third millennium edition, revised and expanded, doi: http://dx.doi.org/10.1007/3-540-44761-X
- [22] Jech, T.: The Axiom of Choice, volume 75 of Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Company, New York, 1973.
- [23] Kalinowski, R., Pil´niak, M., Wo´niak, M.: s z Distinguishing graphs by total colourings, Ars Math. Contemp. 11 , 79-89 (2016). doi: https://doi.org/10.26493/1855-3974.751.9a8
- [24] L´ evy, A.: Basic Set Theory , Dover Publications, Inc., Mineola, NY, 2002, reprint of the 1979 original [Springer, Berlin].
- [25] Loeb, P.: A New Proof of the Tychonoff Theorem, Amer. Math. Monthly 72 , 711-717 (1965). doi: https://doi.org/10.2307/2314411
- [26] Lehner, F., Pil´niak, M., Stawiski. M.: s Distinguishing infinite graphs with bounded degrees, J. Graph Theory 101 , 52-65, (2022). doi: https://doi.org/10.1002/jgt.22809
- [27] Marker, D.: Model Theory: An Introduction , volume 217 of Graduate Texts in Mathematics, Springer-Verlag, New York, 2002. doi: https://doi.org/10.1007/b98860
- [28] Molloy, M., Reed, B.: A bound on the total chromatic number, Combinatorica 18 , 241-280 (1998). doi: https://doi.org/10.1007/PL00009820
- [29] Pil´niak, M., Stawiski, M.: s The optimal general upper bound for the distinguishing index of infinite graphs, J. Graph Theory 93 , 463-469 (2020). doi: https://doi.org/10.1002/jgt.22496

- [30] Soifer, A.: Axiom of choice and chromatic number of R n , J. Comb. Theory Series A 110 , 169-173 (2005). doi: https://doi.org/10.1016/j.jcta.2004.10.004
- [31] Soifer, A., Shelah, S.: Axiom of choice and chromatic number: examples on the plane, J. Comb. Theory Series A 105 , 359-364 (2004). doi: https://doi.org/10.1016/j.jcta.2004.01.001
- [32] Shelah, S., Soifer, A.: Axiom of choice and chromatic number of the plane, J. Comb. Theory Series A 103 , 387-391 (2003). doi: https://doi.org/10.1016/S0097-3165(03)00102-X
- [33] Solovay, R.M.: A Model of Set-Theory in Which Every Set of Reals is Lebesgue Measurable, Ann. of Math. (Ser. 2) 92 , 1-56 (1970). doi: https://doi.org/10.2307/1970696
- [34] Stawiski, M.: The role of the Axiom of Choice in proper and distinguishing colourings, Ars Math. Contemp. 23 (2023), #P3.10. doi: https://doi.org/10.26493/1855-3974.2863.4b9

Alfr´ ed R´nyi Institute of Mathematics, Re´ltanoda utca 13-15, 1053, Budapest, Hungary e a

Email address , Corresponding author: banerjee.amitayu@gmail.com

E¨ otv¨s Lor´nd University, Department of Logic, M´zeum krt. 4, 1088, Budapest, Hungary o a u Email address : mozaag@gmail.com

E¨ otv¨s Lor´nd University, Department of Logic, M´zeum krt. 4, 1088, Budapest, Hungary o a u Email address : alexa279e@gmail.com
Amitayu Banerjee Zalán Molnár Alexa Gopaulsingh
Brooks' type theorems for coloring parameters of locally finite graphs and Konig'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 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)).