The Nagy conjecture on stability for saturated graphs

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

Nagy's 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 on (1o(1))n(1-o(1))n vertices.

This conjecture generalizes the corresponding stability results for saturated complete graphs and odd cycles. The exponent term cannot be improved in the clique case, and for r=2r=2 it cannot be improved for any graph FF because every 3-chromatic graph contains an odd cycle. The conjecture is open in the stated generality.

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.