On the size of $(K_t,K_{1,k})$-co-critical graphs

Abstract

Given graphs $G,H_1,H_2$, we write $G\to (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\nrightarrow (H_1,H_2)$, but $G+e\to (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 $t\ge 3$ and $k\ge 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 $t\in \{3,4,5\}$ and all $k\ge 3$ and $n\ge (2t-2)k+1$. It seems non-trivial to construct extremal $(K_t,K_{1,k})$-co-critical graphs for $t\ge 6$. We also obtain the sharp bound for the size of $(K_3,K_{1,3})$-co-critical graphs on $n\ge 13$ vertices by showing that all such graphs have at least $3n-4$ edges.

arXiv admin note: text overlap with arXiv:1904.07825