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

preprint2022arXivOpen access

Abstract

Given an (r+1)(r+1)-chromatic graph FF and a graph HH that does not contain FF as a subgraph, we say that HH is strictly FF-Turán-good if the Turán graph Tr(n)T_{r}(n) is the unique graph containing the maximum number of copies of HH among all FF-free graphs on nn vertices for every nn large enough. Győri, Pach and Simonovits (1991) proved that cycle C4C_4 of length four is strictly Kr+1K_{r+1}-Turán-good for all r≥2r\geq 2. In this article, we extend this result and show that C4C_4 is strictly FF-Turán-good, where FF is an (r+1)(r+1)-chromatic graph with r≥2r\ge 2 and a color-critical edge. Moreover, we show that every nn-vertex C4C_4-free graph GG with $N(H,G)=\ex(n,C_4,F)-o(n^4)$ can be obtained by adding or deleting o(n2)o(n^2) edges from Tr(n)T_r(n). Our proof uses the flag algebra method developed by Razborov (2007).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.