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