← All problems

Modified clique-free diameter conjecture

6 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. 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)≤(3−2k)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.

References
  1. Éva Czabarka, Inne Singgih and László A. Székely, “On the maximum diameter of k-colorable graphs”, arXiv:2009.02611 (2020).

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.