On a problem concerning integer distance graphs

Abstract

For $D$ being a subset of positive integers, the integer distance graph is the graph $G(D)$, whose vertex set is the set of integers, and edge set is the set of all pairs $uv$ with $|u-v|\in D$. It is known that $\chi (G(D))\le |D|+1$. This article studies the problem (which is motivated by a conjecture of Zhu): "Is it true that $\chi (G(D))=|D|+1$ implies $\omega (G(D))\ge |D|+1$, where $\omega (H)$ is the clique number of $H$?". We give a negative answer to this question, by showing an infinite class of integer distance graphs with $\chi (G(D))=|D|+1$ but $\omega (G(D))=|D|-1$.