On the size of $(K_t,{\mathcal{T}}_k)$-co-critical graphs

Abstract

Given an integer $r\ge 1$ and graphs $G,H_1,\dots ,H_r$, we write $G\to (H_1,\dots ,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,\dots ,r\}$. A non-complete graph $G$ is $(H_1,\dots ,H_r)$-co-critical if $G\nrightarrow (H_1,\dots ,H_r)$, but $G+e\to (H_1,\dots ,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\ge 4$ 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}\lceil \frac{k}{2}\rceil \right)n-c(t,k).$$ Furthermore, this linear bound is asymptotically best possible when $t\in \{4,5\}$ and $k\ge 6$. The method we develop in this paper may shed some light on attacking Hanson and Toft's conjecture.

17 pages, 2 figures