Zorn's Lemma and plane geometry

Question

Given a graph $G$ and a number $n$, Zorn's Lemma immediately implies the existence of a maximal partial coloring of $G$. Equivalently, one may assign $n+1$ colors to the nodes of $G$ such that nodes with the first $n$ colors never lie adjacent, but every node of the last color lies adjacent to at least one node receiving each of the other colors.

In particular, the observation above applies to geometrically determined graphs and even more specifically to graphs on, say, ${\Bbb R}^2$, where one declares two points $p_1$ and $p_2$ adjacent provided that their distance $d(p_1,p_2)$ lies in $D$, some prescribed set of distances.

I would like to know what values of $n$ and $D$ make this existence result not a theorem of ZF. If that asks too much, any example of such an $n$ and $D$ would satisfy me, even better, the simplest possible example (say with $|D|$ as small as possible, and $n$ as small as possible given that).

Answer 1

There are three papers which I believe are highly relevant:

1. "Axiom of choice and chromatic number of the plane", Journal of Combinatorial Theory, Series A Volume 103, Issue 2 , August 2003, Pages 387-391. By S. Shelah and A. Soifer.
2. "Axiom of choice and chromatic number: examples on the plane", Journal of Combinatorial Theory, Series A 105 (2004) 359–364. Also by Shelah-Soifer.
3. "Axiom of choice and chromatic number of ${\mathbb R}^n$, Journal of Combinatorial Theory, Series A 110 (2005) 169 – 173. By Soifer.

They address precisely the kind of question that you have, so I believe you want to take a look at them, although I am not sure they address specifically the question you have.

There is also the nice book by Soifer, "The Mathematical Coloring Book. Mathematics of Coloring and the Colorful Life of its Creators", Springer, 2009. It is not a textbook, in fact, it is very hard to categorize, but it is also very hard to dislike.

The issue addressed in the papers is precisely that choice might have an effect on the chromatic number of infinite graphs, defined geometrically (they give explicit examples, although the graph of distance 1 is not covered by their results, unfortunately). There is a predecessor, K.J. Falconer, "The realization of distances in measurable subsets covering ${\mathbb R}^n$". Comm. Theory (A) 31 (1981), pp. 187–189. Here it is shown that the chromatic number of the plane (the graph of distance 1) is at least 5, provided that the colors are required to be Lebesgue measurable.

Answer 2

There is some recent material by Michael Payne that is also relevant here:

He considers the following variant of the Shelah-Soifer graph: Two points in the plane form an edge if the distance is 1, the $x$-coordinates have rational difference, and the $y$-coordinates have rational difference.

The chromatic number of this graph is 2 (in ZFC). The measurable chromatic number (preimage of colors Lebesgue measurable) is at least 5. If all subsets of the plane are measurable (e.g., in Solovay's model), the chromatic number of this graph is at least 5.

Unfortunately I cannot give you a link to the paper at the very moment. I believe the general problem that you are asking about is open.