Modified clique-free diameter conjecture

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. The graph is assumed to be Kk+1K_{k+1}-free; the source also gives the weaker alternative hypothesis that GG is kk-colorable.

Modified diameter conjecture. Under either the Kk+1K_{k+1}-free hypothesis, or the weaker kk-colorable hypothesis, one should have

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

This modification is proposed after the even-clique case of the earlier conjecture is counterexampled. The paper presents it as a replacement conjecture; the kk-colorable version is explicitly identified as weaker, and no resolution is given.

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, Inne Singgih and László A. Székely, “On the maximum diameter of k-colorable graphs”, arXiv:2009.02611 (2020).

Solutions 0

No solutions have been posted yet.