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

From papers

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 (r1)(3r+2)(r-1)(3r+2), then, as nn\to\infty,

diam(G)2(r1)(3r+2)2r21nδ+O(1)=(322r11(2r1)(2r21))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 3r13r-1, then, as nn\to\infty,

diam(G)3r1rnδ+O(1)=(322r)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.

Progress summary

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

Sources & referencesView supporting material

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.

Solutions 0

No solutions have been posted yet.