View PDF HTML (experimental)

Abstract: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 \nrightarrow ({H}_1, H_2)$ and $G+e\rightarrow ({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\ge6$ 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\ge9$ 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$.

Submission history

From: Zi-Xia Song [view email]
[v1] Wed, 8 Nov 2023 16:19:08 UTC (11 KB)
[v2] Fri, 7 Aug 2026 17:16:31 UTC (11 KB)