The Nagy conjecture on stability for saturated graphs
The Nagy conjecture on stability for saturated graphs
Let be an integer and let be a graph with chromatic number . An -saturated graph is an -free graph to which adding any missing edge creates a copy of . Let denote the number of edges in the Turán graph with parts.
Nagy's conjecture. Every -saturated graph on vertices with edges contains a complete -partite subgraph on 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 it cannot be improved for any graph 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.