Critical graphs for the chromatic edge-stability number

Abstract

The chromatic edge-stability number ${\mathrm{es}}_{\chi }(G)$ of a graph $G$ is the minimum number of edges whose removal results in a spanning subgraph $G^{\prime }$ with $\chi (G^{\prime })=\chi (G)-1$. Edge-stability critical graphs are introduced as the graphs $G$ with the property that ${\mathrm{es}}_{\chi }(G-e)<{\mathrm{es}}_{\chi }(G)$ holds for every edge $e\in E(G)$. If $G$ is an edge-stability critical graph with $\chi (G)=k$ and ${\mathrm{es}}_{\chi }(G)=\ell$, then $G$ is $(k,\ell )$-critical. Graphs which are $(3,2)$-critical and contain at most four odd cycles are classified. It is also proved that the problem of deciding whether a graph $G$ has $\chi (G)=k$ and is critical for the chromatic number can be reduced in polynomial time to the problem of deciding whether a graph is $(k,2)$-critical.