  We prove that Brook's type theorems for several coloring parameters of
infinite graphs, which are true in ZFC, are not provable in ZF (i.e., the
Zermelo-Fraenkel set theory without the Axiom of Choice (AC)). In ZF, we apply
Konig's Lemma (a weak form of AC) and give a combinatorial argument to find a
general upper bound of the total distinguishing number for any connected
infinite graph with finite maximum degree. In ZF, we give new combinatorial
arguments to formulate new conditions for the existence of distinguishing
chromatic number, distinguishing chromatic index, total chromatic number, odd
chromatic number, and neighbor-distinguishing index in infinite locally finite
connected graphs, which are equivalent to Konig's Lemma (any infinite locally
finite connected graph has a ray).
