Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777672 | Journal of Combinatorial Theory, Series B | 2017 | 34 Pages |
Abstract
Balogh, Barát, Gerbner, Gyárfás, and Sárközy proposed a significant strengthening of Lehel's conjecture where Kn is replaced by any graph G with δ(G)>3n/4; if true, this minimum degree condition is essentially best possible. We prove that their conjecture holds when δ(G)>(3/4+o(1))n. Our proof uses Szemerédi's regularity lemma along with the absorbing method of Rödl, RuciÅski, and Szemerédi by first showing that the graph can be covered with monochromatic subgraphs having certain robust expansion properties.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Louis DeBiasio, Luke L. Nelsen,