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).