Czabarka–Singgih–Székely diameter conjecture for graphs with bounded clique number

From papers

Let k3k\geq3, let δ3k21\delta\geq\left\lceil\frac{3k}{2}\right\rceil-1, and let GG be a connected graph of order nn with minimum degree at least δ\delta. Write ω(G)\omega(G) for its clique number and χ(G)\chi(G) for its chromatic number.

Czabarka–Singgih–Székely conjecture. If ω(G)k\omega(G)\leq k, then

diam(G)(32k)nδ+O(1).\operatorname{diam}(G)\leq\left(3-\frac{2}{k}\right)\frac{n}{\delta}+O(1).

A weaker version assumes χ(G)k\chi(G)\leq k instead of ω(G)k\omega(G)\leq k. This updates the earlier conjecture after counterexamples to its even-clique case, but its resolution is not specified in the supplied text.

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

Stijn Cambie and Jorik Jooken, “Sharp results for the Erdős, Pach, Pollack and Tuza problem”, arXiv:2502.08626 (2025).

Solutions 0

No solutions have been posted yet.