Article ID Journal Published Year Pages File Type
8903842 Journal of Combinatorial Theory, Series B 2018 22 Pages PDF
Abstract
For r≥2, we show that every maximal Kr+1-free graph G on n vertices with (1−1r)n22−o(nr+1r) 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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,