nice. we can draw a K_7 on the torus. In fact, I remember a Martin Gardner column with a (non-convex) polyhedron, with the topology of a torus, where each side shared an edge with the other 6! Cris On Apr 3, 2013, at 6:21 PM, Warren D Smith wrote:
As previous posters pointed out, if you want to color the plane so that any 2 points at distance=1 have different colors than you need at least 4 colors (proof:Moser or Golomb's graphs) while 7 colors are known to suffice (proof: tiling by regular hexagons, each monocolored). http://en.wikipedia.org/wiki/Chromatic_number_of_the_plane
I now point out, that if your coloring is required to be PERIODIC and I get to choose the period-parallelogram, then one can prove 7 colors are both necessary and sufficient. Reason is, the tiling of the plane by equilateral triangles, is, in fact, viewed modulo an appropriate period parallelogram, the complete graph K7. Here is a picture drawn by Steven Taschuk: http://amotlpaa.nfshost.com/math/k7torus.html This incidentally also shows that torus graphs can require 7 colors (which also is known to suffice). Meanwhile a hex-tiling construction proves sufficiency.
The catch is, that the period-parallelogram for the "necessary" is not the same as for the "sufficient"!
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cristopher Moore Professor, Santa Fe Institute The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/