The cycle of length four is strictly F-Turán-good

Abstract: Given an

(r + 1)

-chromatic graph

F

and a graph

H

that does not contain

F

as a subgraph, we say that

H

is strictly

F

-Tur'an-good if the Tur'an graph

T_{r} (n)

is the unique graph containing the maximum number of copies of

H

among all

F

-free graphs on

n

vertices for every

n

large enough. GyH{o}ri, Pach and Simonovits (1991) proved that cycle

C_{4}

of length four is strictly

K_{r + 1}

-Tur'{a}n-good for all

r g e q 2

. In this article, we extend this result and show that

C_{4}

is strictly

F

-Tur'an-good, where

F

is an

(r + 1)

-chromatic graph with

r g e 2

and a color-critical edge. Moreover, we show that every

n

-vertex

C_{4}

-free graph

G

with

N (H, G) = e x (n, C_{4}, F) - o (n^{4})

can be obtained by adding or deleting

o (n^{2})

edges from

T_{r} (n)

. Our proof uses the flag algebra method developed by Razborov (2007).

Recommendations

Cites Work

Cited In (1)

This page was built for publication: The cycle of length four is strictly \(F\)-Turán-good