{
  "id": "2208.05386",
  "version": "v1",
  "published": "2022-08-10T15:07:02.000Z",
  "updated": "2022-08-10T15:07:02.000Z",
  "title": "The cycle of length four is strictly $F$-Turán-good",
  "authors": [
    "Doudou Hei",
    "Xinmin Hou"
  ],
  "comment": "16 pages",
  "categories": [
    "math.CO"
  ],
  "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. Gy\\H{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\\geq 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\\ge 2$ and a color-critical edge. Moreover, we show that every $n$-vertex $C_4$-free graph $G$ with $N(H,G)=\\ex(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).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-08-10T15:07:02.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C38"
    ],
    "keywords": [
      "turán-good",
      "chromatic graph",
      "free graph",
      "flag algebra method",
      "turan-good"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}