Erdős–Pach–Pollack–Tuza conjecture on diameters of clique-free graphs
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.
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
Sign in to submit a solution.
No solutions have been posted yet.