Erdős–Pach–Pollack–Tuza conjecture on diameters of clique-free graphs

At least 5 years old · documented by

Let r,δ≥2r,\delta\geq2 be fixed integers, and let GG be a connected graph of order nn and minimum degree δ\delta. Erdős–Pach–Pollack–Tuza conjecture.

(i) If GG is K2rK_{2r}-free and δ\delta is a multiple of (r−1)(3r+2)(r-1)(3r+2), then, as n→∞n\to\infty,

diam⁡(G)≤2(r−1)(3r+2)2r2−1⋅nδ+O(1)=(3−22r−1−1(2r−1)(2r2−1))nδ+O(1).\operatorname{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).

(ii) If GG is K2r+1K_{2r+1}-free and δ\delta is a multiple of 3r−13r-1, then, as n→∞n\to\infty,

diam⁡(G)≤3r−1r⋅nδ+O(1)=(3−22r)nδ+O(1).\operatorname{diam}(G)\leq\frac{3r-1}{r}\cdot\frac{n}{\delta}+O(1)=\left(3-\frac{2}{2r}\right)\frac{n}{\delta}+O(1).

The source says that counterexamples are known in a regime previously left open, so the displayed conjecture is not currently an open conjecture as stated; however, no precise resolution of both clauses is supplied here.

References

Primary source

Jorik Jooken, “Computer-assisted graph theory: a survey”, arXiv:2508.20825 (2025).

Additional references

4 papers in this index state this conjecture (2020–2025). The statement above is taken from the most recent of them; the others are arXiv:2502.08626, arXiv:2109.13887, arXiv:2009.02611.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.