The color-critical-edge stability conjecture for saturated graphs

Let r2r\ge 2 be an integer and let FF be a graph with chromatic number r+1r+1 and a color-critical edge, meaning an edge whose deletion lowers the chromatic number. Let tr(n)t_r(n) denote the number of edges in the Turán graph with rr parts, and let an FF-saturated graph be an FF-free graph to which adding any missing edge creates a copy of FF.

Color-critical-edge stability conjecture. Every FF-saturated graph GG on nn vertices with tr(n)o(nr+1r)t_r(n)-o(n^{\frac{r+1}{r}}) edges contains a complete rr-partite subgraph GG' on (1o(1))n(1-o(1))n vertices.

This is proposed as a weaker version of the general conjecture, restricting FF to graphs with a color-critical edge. The paper presents it as an open proposed version; the full conjecture is proved only for certain 3-chromatic graphs under additional hypotheses.

Sources & referencesView supporting material

Primary source

Dániel Gerbner, “A note on stability for maximal F-free graphs”, arXiv:2101.03223 (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.