Minimizing the number of edges in $(C_4,K_{1,k})$-co-critical graphs

Abstract

Given graphs $H_1,H_2$, a {red, blue}-coloring of the edges of a graph $G$ is a critical coloring if $G$ has neither a red $H_1$ nor a blue $H_2$. A non-complete graph $G$ is $(H_1,H_2)$-co-critical if $G$ admits a critical coloring, but $G+e$ has no critical coloring for every edge $e$ in the complement of $G$. Motivated by a conjecture of Hanson and Toft from 1987, we study the minimum number of edges over all $(C_4,K_{1,k})$-co-critical graphs on $n$ vertices. We show that for all $k\ge 2$ and $n\ge k+\lfloor \sqrt{k-1}\rfloor +2$, if $G$ is a $(C_4,K_{1,k})$-co-critical graph on $n$ vertices, then \[e(G) \ge \frac{(k+2)n}2-3- \frac{(k-1)(k+ \lfloor \sqrt {k-2}\rfloor)}2.\] Moreover, this linear bound is asymptotically best possible for all $k\ge 3$ and $n\ge 3k+4$. It is worth noting that our constructions for the case when $k$ is even have at least three different critical colorings. For $k=2$, we obtain the sharp bound for the minimum number of edges of $(C_4,K_{1,2})$-co-critical graphs on $n\ge 5$ vertices by showing that all such graphs have at least $2n-3$ edges. Our proofs rely on the structural properties of $(C_4,K_{1,k})$-co-critical graphs and a result of Ollmann on the minimum number of edges of $C_4$-saturated graphs.

Version 2 fixes the title and the third author's name arXiv admin note: substantial text overlap with arXiv:2104.13898