Georgia Institute of Technology College of Sciences

Erdős, Pach, Pollack and Tuza conjectured that for fixed integers $r$, $\delta \ge 2$, for any connected graph $G$ with minimum degree $\delta$ and order $n$:

(i) If $G$ is $K_{2r}$-free and $\delta$ is a multiple of $(r-1)(3r+2)$, then, as $n$ tends to infinity, the diameter of $G$ is at most $\frac{2(r-1)(3r+2)}{(2r^2-1)} \cdot \frac{n}{\delta} + O(1)$.

(ii) If $G$ is $K_{2r+1}$-free and $\delta$ is a multiple of $3r-1$, then, as $n$ tends to infinity, the diameter of $G$ is at most $\frac{3r-1}{r} \cdot \frac{n}{\delta} + O(1)$.

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ékely showed that for every connected $4$-colorable graph $G$ of order $n$ and minimum degree $\delta \ge 1$, the diameter of $G$ is at most $\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 prove 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 at least $\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(1)$.

This is joint work with Inne Singgih and László A. Székely.