We show that the diameter of connected $k$-colorable graphs with minimum degree $\geq \delta$ and order $n$ is at most $\left(3-\frac{1}{k-1}\right)\frac{n}{\delta}-1$, while for $k=3$, it is at most $\frac{57n}{23\delta}+O\left(1\right)$.
@article{10_37236_10382,
author = {\'Eva Czabarka and Inne Singgih and L\'aszl\'o A. Sz\'ekely},
title = {On the maximum diameter of \(k\)-colorable graphs},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {3},
doi = {10.37236/10382},
zbl = {1473.05142},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10382/}
}
TY - JOUR
AU - Éva Czabarka
AU - Inne Singgih
AU - László A. Székely
TI - On the maximum diameter of \(k\)-colorable graphs
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/10382/
DO - 10.37236/10382
ID - 10_37236_10382
ER -
%0 Journal Article
%A Éva Czabarka
%A Inne Singgih
%A László A. Székely
%T On the maximum diameter of \(k\)-colorable graphs
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/10382/
%R 10.37236/10382
%F 10_37236_10382
Éva Czabarka; Inne Singgih; László A. Székely. On the maximum diameter of \(k\)-colorable graphs. The electronic journal of combinatorics, Tome 28 (2021) no. 3. doi: 10.37236/10382
