Indeed, the maximum number of a unit distance graph is exactly the chromatic number of the plane. See http://dimacs.rutgers.edu/~hochberg/undopen/graphtheory/graphtheory.html But bizarrely, for infinite unit-distance graphs, this can depend on the axioms of set theory! See http://arxiv.org/abs/0707.1177 - Cris
On Apr 3, 2013, at 3:09 AM, Tom Karzes wrote:
The rhombus construct I suggested implies that any two points separated by sqrt(3)*d must be the same color
I don't think that follows: that's only the case if all pairs of points at distance d are different colors.
But the rhombus does show that, for every d, either there is a pair at distance d or a pair at distance sqrt(3)d with the same color (in any 3-coloring).
The unit-distance graphs (like Moser's and Golomb's) on Wikipedia is interesting:
http://en.wikipedia.org/wiki/Chromatic_number_of_the_plane
But if all distance graphs are 4-colorable, then this technique can't raise the lower bound on the chromatic number of the plane beyond 4. Does anyone know if that's the case? (Note that not all unit-distance graphs are planar.)
Cris