Description
Erd\H{o}s, Pach, Pollack and Tuza [\emph{J. Combin. Theory} {\bf B 47} (1989), 279--285] conjectured that
for fixed integers $r,\delta\geq 2$, for any connected graph $G$ with minimum degree $\delta and order $n$:
\begin{enumerate}
\item If $G$ is $K_{2r}$-free and $\delta$ is a multiple of
$(r-1)(3r+2)$ then, as $n\rightarrow \infty$,
\[ \diam(G) \leq \frac{2(r-1)(3r+2)}{(2r^2-1)}\cdot \frac{n}{\delta} + O(1)=\left(3-\frac{2}{2r-1}-\frac{1}{(2r-1)(2r^2-1)}\right)\frac{n}{\delta}+O(1). \]
\item\label{conpart:odd} If $G$ is $K_{2r+1}$-free and $\delta$ is a multiple of $3r-1$, then, as $n\rightarrow \infty$,
\[ \diam(G) \leq \frac{3r-1}{r}\cdot \frac{n}{\delta} + O(1)=\left(3-\frac{2}{2r}\right)\frac{n}{\delta}+O(1). \]
\end{enumerate}
They created examples that show that the above conjecture, if true, is tight.
No more progress has been reported on this conjecture, except that
for $r=2$ in (ii), under a stronger hypothesis ($4$-colorable instead of $K_5$-free), Czabarka, Dankelman and Sz\'ekely showed that
for every connected $4$-colorable graph $G$ of order $n$ and
minimum degree $\delta\ge 1$, $ \diam(G) \leq \frac{5n}{2\delta}-1.$
For every $r>1$ and $\delta\ge 2(r-1)$, we create $K_{2r}$-free graphs with minimum degree $\delta$ and
diameter $\frac{(6r-5)n}{(2r-1)\delta+2r-3}+O(1)$, which are counterexamples to the
conjecture for every $r>1$ and $\delta>2(r-1)(3r+2)(2r-3)$. We also proves positive results under a stronger hypothesis, $k$-colorability, instead of
being $K_{k+1}$-free. 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}+O(1)$, while for
$k=3$, it is at most $\frac{57n}{23\delta}+O\left(1\right)$.
Tghis is joint work with Inne Singgih and L\'aszl\'o A. Sz\'ekely.
Zoom link: https://zoom.us/j/93088759718?pwd=WFBka2EwcWUxKzI2KzBYVXk0a3JwZz09