wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Could we apply the "Four Color Theorem" 
        
(Message started by: BenVitale on Sep 7^th, 2009, 10:55am)

Title: Could we apply the "Four Color Theorem"
Post by BenVitale on Sep 7^th, 2009, 10:55am

Question :
What is the minimum number of colors needed to color the plane so that no two points of the same color are exact one unit apart?

http://www.mathpuzzle.com/chrompln.html

It is at most 7 ... could it be 4, 5, or 6?

Could it be 4? Could we apply the "Four Color Theorem" here?

http://www.mathpages.com/home/kmath266/kmath266.htm

Title: Re: Could we apply the "Four Color Theorem&qu
Post by Obob on Sep 9^th, 2009, 4:57am

Despite the terminology, the plane is likely not a planar graph (a graph in the plane without crossing edges). At the very least, if it is planar then some wierd embedding in the plane would be needed. If the four color theorem applied, we would have known the answer to be 4 already.

Since no unit-distance graph is known to have chromatic number higher than 4, it is certainly plausible that the number of colors needed could be 4. There is no reason that a coloring of the plane would have to be nearly as nice as the hexagonal coloring that demonstrates 7 colors suffice.