The minimum degree of $(K_s,K_t)$-co-critical graphs

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)$ and $G+e\to (H_1,H_2)$ for every edge $e$ in the complement of $G$. The notion of co-critical graphs was initiated by Ne$\check{s}$et$\check{r}$il in 1986. Galluccio, Simonovits and Simonyi in 1992 proved that every $(K_3,K_3)$-co-critical graph on $n\ge 6$ vertices has minimum degree at least four, and the bound is sharp for all $n\ge 6$. In this paper, we first extend the aforementioned result to all $(K_s,K_t)$-co-critical graphs by showing that every $(K_s,K_t)$-co-critical graph has minimum degree at least $2t+s-5$, where $t\ge s\ge 3$. We then prove that every $(K_3,K_4)$-co-critical graph on $n\ge 9$ vertices has minimum degree at least seven, and the bound is sharp for all $n\ge 9$. This answers a question of the third author in the positive for the case $s=3$ and $t=4$.