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

• DOI: 10.48550/arxiv.2104.13898
• Publication Date: 2021-01-01
• Authors: Hunter Davenport; Zi‐Xia Song; Fan Yang
• Keywords: FOS: Mathematics; Mathematics - Combinatorics; Combinatorics (math.CO)

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