2022/08/30 by Chen, Wanfang, Lu, Changhong, Yuan, Long-Tu
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2208.13995
The Erdős-Simonovits stability theorem is one of the most widely used theorems in extremal graph theory. We obtain an Erdős-Simonovits type stability theorem in multi-partite graphs. Different from the Erdős-Simonovits stability theorem, our stability theorem in multi-partite graphs says that if the number of edges of an H-free graph G is close to the extremal graphs for H, then G has a well-defined structure but may be far away to the extremal graphs for H. As an application, we solve a conjecture posed by Han and Zhao concerning the maximum number of edges in multi-partite graphs which does not contain vertex-disjoint copies of a clique