A Stability Theorem for Maximal C2k+1-free Graphs
Jian WangShipeng WangWeihua YangXiaoli Yuan
所有作者
Jian WangShipeng WangWeihua YangXiaoli Yuan
文献摘要
For any positive integer k, we show that every maximal C2k+1-free
graph with at least n2/4−o(n3/2) edges contains an induced complete
bipartite subgraph on (1−o(1))n vertices. We also show that this is best
possible.