## DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:
DMTCS Conference vol AE (2005), pp. 171-174

## 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

### DMTCS Conference Volume AE (2005), pp. 171-174

author: Javier Barajas and Oriol Serra Distance graphs with maximum chromatic number Distance graphs, chromatic number 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 ≡0 mod 2 and b ≡1 mod 2 . This confirms Zhu's conjecture for |D|=4 . If your browser does not display the abstract correctly (because of the different mathematical symbols) you may look it up in the PostScript or PDF files. Javier Barajas and Oriol Serra (2005), Distance graphs with maximum chromatic number, in 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), Stefan Felsner (ed.), Discrete Mathematics and Theoretical Computer Science Proceedings AE, pp. 171-174 For a corresponding BibTeX entry, please consider our BibTeX-file. dmAE0134.ps.gz (59 K) dmAE0134.ps (136 K) dmAE0134.pdf (141 K)