Article ID Journal Published Year Pages File Type
5777635 Journal of Combinatorial Theory, Series B 2017 38 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,