Amitayu Banerjee: "`Distinguishing number and chromatic number for infinite locally finite connected graphs without the Axiom of Choice.

Amitayu Banerjee.
"`Distinguishing number and chromatic number for infinite locally finite connected graphs without the Axiom of Choice."

Abstract:
 In 1991, Galvin and Komjath proved that ``Any graph has a chromatic number"  is equivalent to the Axiom of Choice (AC) in ZF (i.e., the Zermelo–Fraenkel set theory without AC) using Hartogs’s theorem.  In 1977, Babai introduced distinguishing vertex colorings under the name asymmetric colorings.
We work with simple graphs and observe a combinatorial argument that is different than the one that appeared in Galvin and Komjath's paper, to prove that the following statements are equivalent to Konig's Lemma in ZF:
(a) Any infinite locally finite connected graph has a chromatic number.
(b) Any infinite locally finite connected graph has a distinguishing number.
For the above proofs, we work with Scott's cardinals and assume that the sets of colors can be either well-orderable or non-well-orderable.