Distinguishing colorings, proper colorings, and covering properties without AC
Amitayu Banerjee, Zalán Molnár, Alexa Gopaulsingh · Ars Mathematica Contemporanea · 2024
We work with simple graphs in ZF (i.e., the Zermelo–Fraenkel set theory without the Axiom of Choice (AC)) and assume that the sets of colors can be either well-orderable or non-well-orderable, to prove that the following statements are equivalent to Kőnig’s Lemma: (a) Any infinite locally finite connected graph G such that the minimum degree of G is greater than k, has a chromatic number for any fixed integer k greater than or equal to 2. (b) Any infinite locally finite connected graph has a chromatic index. (c) Any infinite locally finite connected graph has a distinguishing number. (d) Any infinite locally finite connected graph has a distinguishing index. The above results strengthen some recent results of Stawiski since he assumed that the sets of colors can be well-ordered. We formulate new conditions for the existence of irreducible proper coloring, minimal edge cover, maximal matching, and minimal dominating set in connected bipartite graphs and locally finite connected graphs, which are either equivalent to AC or Kőnig’s Lemma. Moreover, we show that if the Axiom of Choice for families of 2-element sets holds, then the Shelah-Soifer graph has a minimal dominating set.