Perhaps a proof theorist can give a truly horrific bound? Charles Greathouse Analyst/Programmer Case Western Reserve University On Wed, Apr 3, 2013 at 7:49 PM, Dan Asimov <dasimov@earthlink.net> wrote:
I do know that it's frequently mentioned that the chromatic number of the [unit-distance graph of the] plane is between 4 and 7, inclusive.
This implies by meta-reasoning that no one has yet found a unit-distance graph of points on the plane that needs more than 4 colors.
(The hexagonal 7-coloring I mentioned recently is the proof that 7 colors suffices, so 7 is an upper bound.) -----
IF there's a unit distance graph of points in the plane that requires 5 colors, say, can one at least find an upper bound on the number of vertices that the smallest such graph -- if any -- would require?
After all, the Moser spindle uses only 7 points. How many more points could a 5-color unit distance graph from the plane possibly need?
--Dan
On 2013-04-03, at 4:24 PM, Cris Moore wrote:
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.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun