Finite $\epsilon$-unit distance graphs

Abstract

In 2005, Exoo posed the following question. Fix $\epsilon$ with $0\leq\epsilon<1$. Let $G_\epsilon$ be the graph whose vertex set is the Euclidean plane, where two vertices are adjacent iff the Euclidean distance between them lies in the closed interval $[1-\epsilon,1+\epsilon]$. What is the chromatic number $\chi(G_\epsilon)$ of this graph? The case $\epsilon=0$ is precisely the classical ``chromatic number of the plane'' problem. In a 2018 preprint, de Grey shows that $\chi(G_0)\geq 5$; the proof relies heavily on machine computation. In 2016, Grytczuk et al. proved a weaker result with a human-comprehensible but nonconstructive proof: whenever $0<\epsilon<1$, we have that $\chi(G_\epsilon)\geq 5$. (This lower bound of $5$ was later improved by Currie and Eggleton to $6$.) The De Bruijn - Erd\H{o}s theorem (which relies on the axiom of choice) then guarantees the existence, for each $\epsilon$, of a finite subgraph $H_\epsilon$ of $G_\epsilon$ such that $\chi(H_\epsilon)\geq 5$. In this paper, we explicitly construct such finite graphs $H_\epsilon$. We find that the number of vertices needed to create such a graph is no more than $2\pi(15+14\epsilon^{-1})^2$. Our proof can be done by hand without the aid of a computer.

Received: 04 August 2020 | Accepted: 31 March 2021