Geodesic
Distance graphs with maximum chromatic number
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005).

Voir la notice de l'article provenant de la source Episciences

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 \equiv 0 (mod 2)$ and $b \equiv 1 (mod 2)$. This confirms Zhu's conjecture for $|D|=4$. 
@article{DMTCS_2005_special_250_a0,
     author = {Barajas, Javier and Serra, Oriol},
     title = {Distance graphs with maximum chromatic number},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
     year = {2005},
     doi = {10.46298/dmtcs.3391},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3391/}
}
TY  - JOUR
AU  - Barajas, Javier
AU  - Serra, Oriol
TI  - Distance graphs with maximum chromatic number
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3391/
DO  - 10.46298/dmtcs.3391
LA  - en
ID  - DMTCS_2005_special_250_a0
ER  - 
%0 Journal Article
%A Barajas, Javier
%A Serra, Oriol
%T Distance graphs with maximum chromatic number
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3391/
%R 10.46298/dmtcs.3391
%G en
%F DMTCS_2005_special_250_a0
Barajas, Javier; Serra, Oriol. Distance graphs with maximum chromatic number. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005). doi : 10.46298/dmtcs.3391. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3391/

Cité par Sources :