A Triangle-free, 4-chromatic ${\mathbb{Q}}^3$ Euclidean Distance Graph Scavenger Hunt!

Abstract

For $d>0$, define $G({\mathbb{Q}}^3,d)$ to be the graph whose set of vertices is the rational space ${\mathbb{Q}}^3$, where two vertices are adjacent if and only if they are a Euclidean distance $d$ apart. Let $\chi ({\mathbb{Q}}^3,d)$ be the chromatic number of such a graph or, in other words, the minimum number of colors needed to color the points of ${\mathbb{Q}}^3$ so that no two points at distance $d$ apart receive the same color. An open problem, originally posed by Benda and Perles in the 1970s, asks if there exists $d$ such that $\chi ({\mathbb{Q}}^3,d)=3$. Through numerous efforts over the years, $\chi ({\mathbb{Q}}^3,d)$ has been determined for many values of $d$, and for all those distances $d$ where $\chi ({\mathbb{Q}}^3,d)$ has not been exactly pinned down, it is known that $\chi ({\mathbb{Q}}^3,d)\in \{3,4\}$. In our work, we detail several search algorithms we have employed to find $4$-chromatic subgraphs of various graphs $G({\mathbb{Q}}^3,d)$ whose chromatic number was previously unknown. Ultimately, we conjecture that no $3$-chromatic $G({\mathbb{Q}}^3,d)$ exists. Along the way, we pose a few related questions that we feel are of interest in their own right.