On the Chromatic Number of the Plane with Two Forbidden Distances

Abstract

The Chromatic Number of the Plane (CNP) problem can be generalized to the CNP with two forbidden distances. This problem seeks the smallest number of colors sufficient for coloring the Euclidean plane such that no two points at distance 1 or at distance d have the same color. A lower bound of six has previously been established for 𝑑=1+√5 2 and 𝑑=2 by constructing a 6-chromatic 2-distance graph with edge lengths 1 and d. Here, we construct a 6-chromatic 2-distance graph for two new values, 𝑑= √2+√6 2 and 𝑑=√3. This way, the lower bound for the CNP with two forbidden distances 1 and d is raised to six, for the two new values of d. We then minimize the number of vertices in our 6-chromatic 2-distance graphs. For 𝑑=√2+√6 2 and 𝑑=√3, the smallest results are a 117-vertex graph and a 33-vertex graph, respectively. The latter graph has only two vertices more than the smallest known 6-chromatic 2-distance graph. Both the verification of the 6-chromaticity and the graph minimization process were assisted by the use of a SAT solver.