Distance graphs with maximum chromatic number

Oriol Serra¹

Universitat Politècnica de Catalunya

Let $D$ be a finite set of integers. The distance graph $G(D)$ has the set of integers as vertices and two vertices at distance $d\in D$ are adjacent in $G(D)$. A conjecture of Xuding Zhu states that if the chromatic number of $G(D)$ achieves its maximum value $\vert D\vert+1$ then the graph has a clique of order $\vert D\vert$. We prove that the chromatic number of a distance graph with $D=\{ a,b,c,d\}$ is five if and only if either $D=\{ 1,2,3,4k\}$ or $D=\{ a,b,a+b,a+2b\}$. This confirms Zhu's conjecture for $\vert D\vert=4$.

Footnotes

... Serra¹

joint work with Javier Barajas