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

From papers

Let k3k\geq 3, let δ3k21\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)(32k)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.

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

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

Solutions 0

No solutions have been posted yet.