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

Summary: Given an integer \(r\geqslant 1\) 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 \textit{D. Hanson} and \textit{B. Toft}'s conjecture [J. Graph Theory 11, No. 2, 191--196 (1987; Zbl 0669.05032)], 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 \textit{A. N. Day} [Comb. Probab. Comput. 26, No. 2, 201--207 (2017; Zbl 1371.05140)], we apply graph bootstrap percolation on a not necessarily \(K_t\)-saturated graph to prove that for all \(t\geqslant 4\) and \(k\geqslant\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)\geqslant \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\geqslant 6\). The method we develop in this paper may shed some light on attacking Hanson and Toft's conjecture [loc. cit.].