MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Hi David. I assume you are familiar with the results of Shelah-Soifer? – Andrés E. Caicedo Nov 17 '10 at 18:40
Hi Andres, tell or send a citation please? – David Feldman Nov 17 '10 at 18:54
Okay, found it. – David Feldman Nov 17 '10 at 18:58

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.

share|cite|improve this answer

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.

share|cite|improve this answer
Hmm. I didn't know about this one. I'll have to look for it. – Andrés E. Caicedo Nov 17 '10 at 19:26
Found it: Michael S. Payne, "Unit Distance Graphs with Ambiguous Chromatic Number", The Electronic Journal of Combinatorics, vol 16 (1), 2009. You can read the abstract and download it here: – Andrés E. Caicedo Nov 18 '10 at 2:57
Thanks. I was at home and could not access MathSciNet. Didn't find it using google. – Stefan Geschke Nov 18 '10 at 7:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.