Surviving instances of the Erdős–Pach–Pollack–Tuza diameter conjecture: sharp bounds for the diameter of connected $K_{k+1}$-free graphs of given minimum degree for $k \le 6$

In 1989 Erdős, Pach, Pollack and Tuza proved that every connected $n$-vertex graph of minimum degree $\delta$ has diameter at most $3n/(\delta+1) + O(1)$, determined the sharp asymptotic maximum diameter for triangle-free and $C_4$-free graphs, and conjectured sharp bounds when a larger clique is forbidden: a connected $K_{2r+1}$-free graph with $\delta$ a multiple of $3r-1$ should have diameter at most $\frac{3r-1}{r}\cdot\frac{n}{\delta} + O(1)$, with an analogous bound for $K_{2r}$-free graphs. Later work disproved the $K_{2r}$-free part for every $r \ge 2$, proved the $k$-colorable analogue of the parity-unified Czabarka–Singgih–Székely reformulation for $k \in \{3,4\}$, and a 2026 preprint of Chen–Chen disproves that reformulation for every $k \ge 7$ in both its $K_{k+1}$-free and $k$-colorable versions, refuting the 1989 conjecture for $r \ge 4$. What survives is precisely the $K_{k+1}$-free instances with $k \in \{3,4,5,6\}$ — including the two instances native to the 1989 conjecture, $K_5$-free graphs (coefficient $5/2$) and $K_7$-free graphs (coefficient $8/3$) — plus the $k$-colorable instances $k \in \{5,6\}$. The problem is to settle these instances: prove $\operatorname{diam}(G) \le (3 - \frac{2}{k})\frac{n}{\delta} + O(1)$ for all connected $K_{k+1}$-free graphs of minimum degree at least $\delta$, or exhibit counterexample families.

Background

In this area, a graph $G$ has order $n = |V(G)|$ (its number of vertices), minimum degree $\delta$ (the least number of neighbors of a vertex), and, when connected, diameter $\operatorname{diam}(G)$ (the largest number of edges on a shortest path between two of its vertices). A graph is $K_t$-free if it contains no $K_t$, a complete subgraph (clique) on $t$ vertices; equivalently, its clique number $\omega(G)$ is at most $t-1$. It is $k$-colorable if its vertices split into $k$ independent sets, i.e. its chromatic number $\chi(G)$ is at most $k$. Every $k$-colorable graph is $K_{k+1}$-free, so forbidding the clique is the weaker and more general hypothesis. The bounds below are asymptotic in $n \to \infty$ with $k$ and $\delta$ fixed, stated up to an additive $O(1)$ constant; a bound is called sharp when its coefficient of $n/\delta$ cannot be reduced, which is demonstrated by explicit infinite graph sequences, usually blow-ups of a small template graph (replace each template vertex by a complete graph or an independent set, and join two parts completely or not at all).

A classical result, discovered independently several times, states that every connected $n$-vertex graph of minimum degree $\delta \ge 2$ satisfies $\operatorname{diam}(G) \le \frac{3n}{\delta+1} + O(1)$; this is sharp even for $\delta$-regular graphs, but the extremal examples contain cliques whose order grows with $\delta$. Erdős, Pach, Pollack and Tuza asked in 1989 what improves when large cliques are forbidden. They proved the sharp bound $\frac{2n}{\delta} + O(1)$ for triangle-free graphs ($\omega \le 2$) and likewise determined the sharp asymptotic maximum diameter for $C_4$-free graphs (graphs with no 4-cycle), and they conjectured two families of sharp bounds for larger forbidden cliques, each accompanied by their own constructions showing that the conjectured coefficient would be sharp:

(i) if $G$ is connected, $K_{2r}$-free, of order $n$ and minimum degree $\delta$ a multiple of $(r-1)(3r+2)$, then $\operatorname{diam}(G) \le \frac{2(r-1)(3r+2)}{2r^2-1}\cdot\frac{n}{\delta} + O(1)$;

(ii) if $G$ is connected, $K_{2r+1}$-free, of order $n$ and minimum degree $\delta$ a multiple of $3r-1$, then $\operatorname{diam}(G) \le \frac{3r-1}{r}\cdot\frac{n}{\delta} + O(1)$.

Part (ii) at $r = 1$ is exactly their triangle-free theorem, and the coefficient in (ii) equals $3 - \frac{2}{k}$ at $k = 2r$.

Part (i) is now known to be false for every $r \ge 2$ (for all admissible $\delta > 2(r-1)(3r+2)(2r-3)$, and also at the boundary point $r = 2$, $\delta = 16$), so Czabarka–Singgih–Székely proposed the parity-unified reformulation the field now uses: $(C_k)$: for every $k \ge 3$ and $\delta \ge \lceil 3k/2 \rceil - 1$, every connected $K_{k+1}$-free (weaker version: $k$-colorable) graph of order $n$ and minimum degree at least $\delta$ satisfies $\operatorname{diam}(G) \le (3 - \frac{2}{k})\frac{n}{\delta} + O(1)$. For even $k = 2r$ with $3r-1$ dividing $\delta$, this contains part (ii) exactly. Later progress: the $k$-colorable version of $(C_k)$ is a theorem for $k \in \{3,4\}$, with the explicit bound $\operatorname{diam}(G) \le (3 - \frac{2}{k})\frac{n}{\delta} - 1$, proved by a linear-programming duality argument on an auxiliary weighted graph decomposition (clump graphs); and a 2026 preprint of Chen–Chen disproves $(C_k)$ for every $k \ge 7$ in both versions — thereby refuting part (ii) for $r \ge 4$ at large admissible $\delta$ — via blow-ups of weighted layered clique graphs (graphs whose vertices are partitioned into ordered layers, two vertices being adjacent exactly when they lie in the same or in consecutive layers). Those refutations exploit the slack between the conjectured coefficient and the exact optima at fixed $\delta$. In the refined fixed-$\delta$ language of Cambie–Jooken, $f(\delta)$ (resp. $f'(\delta)$) is the smallest constant such that $\operatorname{diam}(G) \le f(\delta)\,n + O(1)$ for all graphs of minimum degree $\delta$ and clique number at most $3$ (resp. chromatic number at most $3$); they determined $f(\delta)$ for $\delta = 4, 5, 6$ and $f'(\delta)$ for $\delta = 7, 8$, and conjectured $f(\delta) = f'(\delta)$.

No published or preprinted work resolves the $K_{k+1}$-free version of $(C_k)$ in general for $k \in \{3,4,5,6\}$: that is, part (ii) of the 1989 conjecture at $r = 2$ ($K_5$-free graphs, coefficient $\frac{5}{2}$) and $r = 3$ ($K_7$-free graphs, coefficient $\frac{8}{3}$), together with the odd instances $k = 3$ ($K_4$-free, coefficient $\frac{7}{3}$) and $k = 5$ ($K_6$-free, coefficient $\frac{13}{5}$) added by the reformulation. The $k = 3$ instance is not untouched: its sharp lower-bound family is already known (Czabarka–Singgih–Székely), and its fixed-$\delta$ optima are determined for $\delta = 4, 5, 6$ (Cambie–Jooken), so that instance likewise reduces to the general-$\delta$ upper bound. In the weaker colorable version, exactly the instances $k \in \{5,6\}$ remain. These are the surviving cases of the 1989 question.

Problem Statement

Determine the asymptotically sharp upper bound for the diameter of connected graphs with no $K_{k+1}$ subgraph and given minimum degree, for each remaining clique size $k \in \{3,4,5,6\}$. Concretely, prove or disprove the $K_{k+1}$-free version of the Czabarka–Singgih–Székely conjecture for these $k$: for fixed $k \in \{3,4,5,6\}$ and $\delta \ge \lceil 3k/2 \rceil - 1$, is there a constant $C$, allowed to depend on the fixed $k$ and $\delta$, such that every connected $K_{k+1}$-free graph $G$ of order $n$ and minimum degree at least $\delta$ satisfies

$$\operatorname{diam}(G) \le \left(3 - \frac{2}{k}\right)\cdot\frac{n}{\delta} + C$$

for all $n$?

The two instances native to the 1989 Erdős–Pach–Pollack–Tuza conjecture are $k = 4$ and $k = 6$: every connected $K_{2r+1}$-free graph of order $n$ and minimum degree $\delta$ (with $\delta$ a multiple of $3r-1$) should have $\operatorname{diam}(G) \le \frac{3r-1}{r}\cdot\frac{n}{\delta} + O(1)$ for $r = 2$ ($K_5$-free graphs, coefficient $\frac{5}{2}$) and $r = 3$ ($K_7$-free graphs, coefficient $\frac{8}{3}$). The instances $k = 3$ ($K_4$-free, coefficient $\frac{7}{3}$) and $k = 5$ ($K_6$-free, coefficient $\frac{13}{5}$) are the odd-clique cases added by the reformulation and have the same open status. The weaker $k$-colorable version remains open exactly for $k \in \{5,6\}$; it is implied by the corresponding $K_{k+1}$-free instance, since every $k$-colorable graph is $K_{k+1}$-free.

The conjectured sharp coefficient $3 - \frac{2}{k}$ is attained by the known lower-bound constructions. A disproof of the bound is an infinite family of connected $K_{k+1}$-free graphs with minimum degree at least $\delta$ whose diameter exceeds $(3 - \frac{2}{k})\frac{n}{\delta}$ by an unbounded amount.

References

1. Paul Erdős, János Pach, Richard Pollack, Zsolt Tuza, Radius, diameter, and minimum degree, Journal of Combinatorial Theory, Series B 47(1) (1989) 73–79, doi:10.1016/0095-8956(89)90066-X, https://doi.org/10.1016/0095-8956(89)90066-X (source of the conjectures; primary full text paywalled)
2. Éva Czabarka, P. Dankelmann, László A. Székely, Diameter of 4-colourable graphs, European Journal of Combinatorics 30 (2009) 1082–1089, doi:10.1016/j.ejc.2008.09.005, https://doi.org/10.1016/j.ejc.2008.09.005
3. Éva Czabarka, Inne Singgih, László A. Székely, On the Maximum Diameter of k-Colorable Graphs, The Electronic Journal of Combinatorics 28 (2021), doi:10.37236/10382, https://doi.org/10.37236/10382 (preprint: arXiv:2009.02611, https://arxiv.org/abs/2009.02611)
4. Éva Czabarka, Inne Singgih, László A. Székely, Counterexamples to a conjecture of Erdős, Pach, Pollack and Tuza, Journal of Combinatorial Theory, Series B 151 (2021) 38–45, doi:10.1016/j.jctb.2021.06.001, https://doi.org/10.1016/j.jctb.2021.06.001
5. Éva Czabarka, Stephen J. Smith, László A. Székely, Maximum diameter of 3- and 4-colorable graphs, Journal of Graph Theory 102 (2023) 262–270, doi:10.1002/jgt.22869, https://doi.org/10.1002/jgt.22869 (preprint: arXiv:2109.13887, https://arxiv.org/abs/2109.13887)
6. Stijn Cambie, Jorik Jooken, Sharp results for the Erdős, Pach, Pollack and Tuza problem, arXiv:2502.08626 (2025), doi:10.48550/arXiv.2502.08626, https://arxiv.org/abs/2502.08626 (unpublished preprint)
7. Hangdi Chen, Yaojun Chen, Counterexamples to two conjectures on the diameter of clique-free graphs, arXiv:2609.03346 (2026), doi:10.48550/arXiv.2609.03346, https://arxiv.org/abs/2609.03346 (preprint of 3 September 2026, not yet peer-reviewed)