Supersaturation problem for color-critical graphs
<p dir="ltr">The <i>Turán function</i> ex ( <i>n , F</i> ) of a graph F is the maximum number of edges in an F-free graph with n vertices. The classical results of Turán and Rademacher from 1941 led to the study of supersaturated graphs where the key question...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | |
| منشور في: |
2017
|
| الموضوعات: | |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| الملخص: | <p dir="ltr">The <i>Turán function</i> ex ( <i>n , F</i> ) of a graph F is the maximum number of edges in an F-free graph with n vertices. The classical results of Turán and Rademacher from 1941 led to the study of supersaturated graphs where the key question is to determine<i> h </i><sub><em>F</em></sub><i> </i>( <i>n , q </i>) , the minimum number of copies of F that a graph with n vertices and ex ( <i>n , F</i> ) + <i>q</i> edges can have. We determine <i>h F</i> ( <i>n , q </i>) asymptotically when F is color-critical (that is, F contains an edge whose deletion reduces its chromatic number) and <i>q</i> = o ( n<sup>2</sup> ) . Determining the exact value of h F ( <i>n , q </i>) seems rather difficult. For example, let c 1 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 c 1 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 c 1 > 0 for every color-critical F. Our approach also allows us to determine c 1 for a number of graphs, including odd cycles, cliques with one edge removed, and complete bipartite graphs plus an edge.</p><h2 dir="ltr">Other Information</h2><p dir="ltr">Published in: Journal of Combinatorial Theory, Series B<br>License: <a href="http://creativecommons.org/licenses/by/4.0/" target="_blank">http://creativecommons.org/licenses/by/4.0/</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.1016/j.jctb.2016.12.001" target="_blank">https://dx.doi.org/10.1016/j.jctb.2016.12.001</a></p> |
|---|