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 ∈D$ are adjacent in $G(D)$. A conjecture of Xuding Zhu states that if the chromatic number of $G (D)$ achieves its maximum value $|D|+1$ then the graph has a clique of order $|D|$. 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\}$ with $a \equiv 0 (mod 2)$ and $b \equiv 1 (mod 2)$. This confirms Zhu's conjecture for $|D|=4$.
V. Ďuriš;T. Šumný;D. Gonda;T. Lengyelfalusy, 2022, Solving Lonely Runner Conjecture through differential geometry, Journal of Applied Mathematics Statistics and Informatics, 18, 1, pp. 21-28, 10.2478/jamsi-2022-0002, https://doi.org/10.2478/jamsi-2022-0002.
Ram Krishna Pandey;Neha Rai, 2021, Density of sets with missing differences and applications, Mathematica Slovaca, 71, 3, pp. 595-614, 10.1515/ms-2021-0006.
Ram Krishna Pandey;Neha Rai, 2020, Maximal Density of Sets with Missing Differences and Various Coloring Parameters of Distance Graphs, Taiwanese Journal of Mathematics, 24, 6, 10.11650/tjm/200403, https://doi.org/10.11650/tjm/200403.
Daphne Der-Fen Liu;Aileen Sutedja, 2012, Chromatic number of distance graphs generated by the sets {2,3,x,y}, Journal of Combinatorial Optimization, 25, 4, pp. 680-693, 10.1007/s10878-012-9509-4.
Aleksandar Ilić;Milan Bašić, 2010, On the chromatic number of integral circulant graphs, arXiv (Cornell University), 60, 1, pp. 144-150, 10.1016/j.camwa.2010.04.041.
Javier Barajas;Oriol Serra, 2009, On the chromatic number of circulant graphs, Discrete Mathematics, 309, 18, pp. 5687-5696, 10.1016/j.disc.2008.04.041.
Javier Barajas;Oriol Serra, 2007, Regular chromatic number and the lonely runner problem, Electronic Notes in Discrete Mathematics, 29, pp. 479-483, 10.1016/j.endm.2007.07.085.