Chromatic properties of the Euclidean plane

Abstract

Let $G$ be the unit distance graph in the plane. A well-known problem in combinatorial geometry is that of determining the chromatic number of $G$. It is known that $4\le \chi (G)\le 7$. The upper bound of 7 is obtained using tilings of the plane. The present paper studies two problems where we seek proper colourings of $G$, adding restrictions inspired by tilings: Let $H(\epsilon )$ be the graph whose vertices are the points of ${\mathbb{R}}^2$, with an edge between two points if their distance lies in the interval $[1,1+\epsilon ]$. We show that for small $\epsilon$, $0<\epsilon \le \frac{3\sqrt{2}}{4}-1$, we have $6\le \chi (H(\epsilon ))\le 7$. This improves the result of Exoo and Grytczuk et al. that $5\le \chi (H(\epsilon ))$ for small $\epsilon$. Suppose that $G$ is properly coloured, but so that two solidly coloured regions meet along a straight line in some neighbourhood. Then at least 5 colours must be used.

11 pages, 6 figures. Reference to Grytczuk et al. added, March 22, 2016

Cited by in corpus (1)

• On the cromatic number of infinitesimal plane layer