# Distance graphs with maximum chromatic number

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

- ... Serra
^{1}
- joint work with Javier Barajas

2005-05-23