Given graphs $G, H_1, H_2$, we write $G rightarrow ({H}_1, H_2)$ if every ${$red, blue$}$-coloring of the edges of $G$ contains a red copy of $H_1$ or a blue copy of $H_2$. A non-complete graph $G$ is $(H_1, H_2)$-co-critical if $G rightarrow ({H}_1, H_2)$, but $G+erightarrow ({H}_1, H_2)$ for every edge $e$ in $overline{G}$. Motivated by a conjecture of Hanson and Toft from 1987, we study the minimum number of edges over all $(K_t, K_{1,k})$-co-critical graphs on $n$ vertices. We prove that for all $tge3$ and $kge 3$, there exists a constant $ell(t, k)$ such that, for all $n ge (t-1)k+1$, if $G$ is a $(K_t, K_{1,k})$-co-critical graph on $n$ vertices, then $$ e(G)ge left(2t-4+frac{k-1}{2}right)n-ell(t, k).$$ Furthermore, this linear bound is asymptotically best possible when $tin{3, 4,5}$ and all $kge3$ and $nge (2t-2)k+1$. It seems non-trivial to construct extremal $(K_t, K_{1,k})$-co-critical graphs for $tge6$. We also obtain the sharp bound for the size of $(K_3, K_{1,3})$-co-critical graphs on $nge13$ vertices by showing that all such graphs have at least $3n-4$ edges.
تحميل البحث