Erdős–Pach–Pollack–Tuza conjecture on diameters of clique-free graphs
Let be fixed integers, and let be a connected graph of order and minimum degree . Erdős–Pach–Pollack–Tuza conjecture.
(i) If is -free and is a multiple of , then, as ,
(ii) If is -free and is a multiple of , then, as ,
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
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.