Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777635 | Journal of Combinatorial Theory, Series B | 2017 | 38 Pages |
Abstract
Determining the exact value of hF(n,q) seems rather difficult. For example, let c1 be the limit superior of q/n for which the extremal structures are obtained by adding some q edges to a maximum F-free graph. The problem of determining c1 for cliques was a well-known question of ErdÅs that was solved only decades later by Lovász and Simonovits. Here we prove that c1>0 for every color-critical F. Our approach also allows us to determine c1 for a number of graphs, including odd cycles, cliques with one edge removed, and complete bipartite graphs plus an edge.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Oleg Pikhurko, Zelealem B. Yilma,