On the Chromatic Vertex Stability Number of Graphs

Abstract

The chromatic vertex (resp.\ edge) stability number ${\mathrm{vs}}_{\chi }(G)$ (resp.\ ${\mathrm{es}}_{\chi }(G)$) of a graph $G$ is the minimum number of vertices (resp.\ edges) whose deletion results in a graph $H$ with $\chi (H)=\chi (G)-1$. In the main result it is proved that if $G$ is a graph with $\chi (G)\in \{\Delta (G),\Delta (G)+1\}$, then ${\mathrm{vs}}_{\chi }(G)={\mathrm{ivs}}_{\chi }(G)$, where ${\mathrm{ivs}}_{\chi }(G)$ is the independent chromatic vertex stability number. The result need not hold for graphs $G$ with $\chi (G)\le \frac{\Delta (G)+1}{2}$. It is proved that if $\chi (G)>\frac{\Delta (G)}{2}+1$, then ${\mathrm{vs}}_{\chi }(G)={\mathrm{es}}_{\chi }(G)$. A Nordhaus-Gaddum-type result on the chromatic vertex stability number is also given.