Sharp results for the Erdős, Pach, Pollack and Tuza problem

Abstract

We consider the Erdős, Pach, Pollack and Tuza problem, asking for the maximum diameter of a graph with given order $n$, minimum degree $\delta$ and clique number at most $\omega$. We solve their problem asymptotically for the first hard case, $\omega \le 3$, for the smallest values of $\delta$ by determining the smallest rational number $f(\delta )$ such that $diam(G)\le f(\delta )n+O(1)$ for all graphs $G$ with order $n$, minimum degree $\delta$ and clique number $\omega \le 3$. We also consider the weaker version where the clique number $\omega \le 3$ is replaced by having chromatic number $\chi \le 3$ and solve this version for small $\delta$, thereby yielding a counterexample to a conjecture of Erdős et al. in a regime where this conjecture was still open. When restricting the conjecture to graphs with chromatic number $\chi \le 3$, we show that this counterexample appears for the smallest possible $\delta$, namely $\delta =16.$

arXiv comment16 pages (out of which 5 are appendix), 4 figures