| Abstrakt: |
Given an (r+1)-chromatic graph Fand a graph Hthat does not contain Fas a subgraph, we say that His strictly F-Turán-good if the Turán graph Tr(n)is the unique graph containing the maximum number of copies of Hamong all F-free graphs on nvertices for every nlarge enough. Györi et al. (Graphs Comb 7(1):31–37, 1991) proved that cycle C4of length four is strictly Kr+1-Turán-good for all r≥2. In this article, we extend this result and show that C4is strictly F-Turán-good, where Fis an (r+1)-chromatic graph with r≥2and a color-critical edge. Moreover, we show that every n-vertex F-free graph Gwith N(C4,G)=ex(n,C4,F)-o(n4)can be obtained by adding or deleting o(n2)edges from Tr(n). Our proof uses the flag algebra method developed by Razborov (J Symb Logic 1239–1282, 2007). |
Full text from SpringerLink