Czabarka–Dankelmann–Székely conjecture on diameters of clique-free graphs

About 5 years old · traced to

Let k≥3k\geq 3, let δ≥⌈3k2⌉−1\delta\geq \left\lceil\frac{3k}{2}\right\rceil-1, and let GG be a connected graph of order nn and minimum degree at least δ\delta. A graph is Kk+1K_{k+1}-free if it contains no complete subgraph on k+1k+1 vertices; the source also mentions the stronger hypothesis that GG is kk-colorable.

Czabarka–Dankelmann–Székely conjecture. For every such GG,

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

This modified conjecture was proposed after the even-clique case of the earlier conjecture was disproved. It removes the parity distinction between excluded complete subgraphs; the source does not report a resolution.

References

Primary source

Éva Czabarka, Stephen J. Smith and László Székely, “Maximum diameter of 3- and 4-colorable graphs”, arXiv:2109.13887 (2021).

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.