← All problems

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

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
  1. 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.