On critical graphs for the chromatic edge-stability number

Abstract

The {\em chromatic edge-stability number} $e{s}_{\chi }(G)$ of a graph $G$ is the minimum number of edges whose removal results in a spanning subgraph with the chromatic number smaller than that of $G$. A graph $G$ is called {\em $(3,2)$-critical} if $\chi (G)=3$, $e{s}_{\chi }(G)=2$ and for any edge $e\in E(G)$, $e{s}_{\chi }(G-e)<e{s}_{\chi }(G)$. In this paper, we characterize $(3,2)$-critical graphs which contain at least five odd cycles. This answers a question proposed by Brešar, Klavžar and Movarraei in [Critical graphs for the chromatic edge-stability number, {\it Discrete Math.} {\bf 343}(2020) 111845].

12 pages, 2 figures