{
  "id": "1904.07825",
  "version": "v1",
  "published": "2019-04-16T17:04:24.000Z",
  "updated": "2019-04-16T17:04:24.000Z",
  "title": "On the size of $(K_t,\\mathcal{T}_k)$-co-critical graphs",
  "authors": [
    "Zi-Xia Song",
    "Jingmei Zhang"
  ],
  "comment": "17 pages, 2 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "Given an integer $r\\ge1$ and graphs $G, H_1, \\ldots, H_r$, we write $G \\rightarrow ({H}_1, \\ldots, {H}_r)$ if every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H_i$ in color $i$ for some $i\\in\\{1, \\ldots, r\\}$. A non-complete graph $G$ is $(H_1, \\ldots, H_r)$-co-critical if $G \\nrightarrow ({H}_1, \\ldots, {H}_r)$, but $G+e\\rightarrow ({H}_1, \\ldots, {H}_r)$ for every edge $e$ in $\\overline{G}$. In this paper, motivated by Hanson and Toft's conjecture [Edge-colored saturated graphs, J Graph Theory 11(1987), 191--196], we study the minimum number of edges over all $(K_t, \\mathcal{T}_k)$-co-critical graphs on $n$ vertices, where $\\mathcal{T}_k$ denotes the family of all trees on $k$ vertices. Following Day [Saturated graphs of prescribed minimum degree, Combin. Probab. Comput. 26 (2017), 201--207], we apply graph bootstrap percolation on a not necessarily $K_t$-saturated graph to prove that for all $t\\ge4 $ and $k\\ge \\max\\{6, t\\}$, there exists a constant $c(t, k)$ such that, for all $n \\ge (t-1)(k-1)+1$, if $G$ is a $(K_t, \\mathcal{T}_k)$-co-critical graph on $n$ vertices, then $$ e(G)\\ge \\left(\\frac{4t-9}{2}+\\frac{1}{2}\\left\\lceil \\frac{k}{2} \\right\\rceil\\right)n-c(t, k).$$ Furthermore, this linear bound is asymptotically best possible when $t\\in\\{4,5\\}$ and $k\\ge6$. The method we develop in this paper may shed some light on attacking Hanson and Toft's conjecture.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-04-16T17:04:24.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "co-critical graph",
      "saturated graph",
      "tofts conjecture",
      "apply graph bootstrap percolation",
      "minimum number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}