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.

  • 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.