Distance graphs with maximum chromatic number Original Research Article

The distance graph image has the set of integers as vertices and two vertices are adjacent in image if their difference is contained in the set image. A conjecture of Zhu states that if the chromatic number of image achieves its maximum value image then the graph has a triangle. The conjecture is proven to be true if image. We prove that the chromatic number of a distance graph with image is five only if either image or image. This confirms a stronger version of Zhuʹs conjecture for image, namely, if the chromatic number achieves its maximum value then the graph contains image.