# Distance graphs with maximum chromatic number

Oriol Serra1

Universitat Politècnica de Catalunya

Let be a finite set of integers. The distance graph has the set of integers as vertices and two vertices at distance are adjacent in . A conjecture of Xuding Zhu states that if the chromatic number of achieves its maximum value then the graph has a clique of order . We prove that the chromatic number of a distance graph with is five if and only if either or . This confirms Zhu's conjecture for .

#### Footnotes

... Serra1
joint work with Javier Barajas

2005-05-23