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

About 1 year old · traced to

Let k≥3k\geq3, let δ≥⌈3k2⌉−1\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)≤(3−2k)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.

References

Primary source

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

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.