A stability theorem for maximal Kr+1-free graphs

作者：Popielar Kamil^*; Sahasrabudhe Julian; Snyder Richard

来源：Journal of Combinatorial Theory - Series B, 2018, 132: 236-257.

DOI：10.1016/j.jctb.2018.04.001

• Stability
• Saturation
• Kr-free graphs
• Erdos-Simonovits
• Turan-type problem

For r >= 2, we show that every maximal Kr+1-free graph G on n vertices with (1-1/r)n(2)/2 - o(n(r+1/r)) edges contains a complete r-partite subgraph on (1-o(1))n vertices. We also show that this is best possible. This result answers a question of Tyomkyn and Uzzell.

• 出版日期2018-9