The color-critical-edge stability conjecture for saturated graphs
The color-critical-edge stability conjecture for saturated graphs
Let be an integer and let be a graph with chromatic number and a color-critical edge, meaning an edge whose deletion lowers the chromatic number. Let denote the number of edges in the Turán graph with parts, and let an -saturated graph be an -free graph to which adding any missing edge creates a copy of .
Color-critical-edge stability conjecture. Every -saturated graph on vertices with edges contains a complete -partite subgraph on vertices.
This is proposed as a weaker version of the general conjecture, restricting 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
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.