Given an integer $rge1$ 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 $iin{1, ldots, r}$. A non-complete graph $G$ is $(H_1, ldots, H_r)$-co-critical if $G rightarrow ({H}_1, ldots, {H}_r)$, but $G+erightarrow ({H}_1, ldots, {H}_r)$ for every edge $e$ in $overline{G}$. In this paper, motivated by Hanson and Tofts 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 $tge4 $ and $kge 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}leftlceil frac{k}{2} rightrceilright)n-c(t, k).$$ Furthermore, this linear bound is asymptotically best possible when $tin{4,5}$ and $kge6$. The method we develop in this paper may shed some light on attacking Hanson and Tofts conjecture.
تحميل البحث