0
$\begingroup$

Suppose $G$ is the simple graph with vertex set $\mathbb{R}^2$ created by connecting two points iff they are distance one from each other in the plane. How can we prove that $4\le \chi(G)\le7$? I think I have seen this problem somewhere before but can't pinpoint it. No hints please.

  • 4
    http://en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_problem2012-07-05
  • 0
    I have no idea where to start and I am told it is a known result so I'd be curious to see it. :)2012-07-05
  • 1
    Wasn't this question just posted?2012-07-06

1 Answers 1

1

The fact that there is a $4$-chromatic unit distance graph implies that $\chi \geq 4$, while the appropriate colouring of a hexagonal tiling shows that $\chi \leq 7$. For details, here's the Wikipedia article.