Some extremal results on the chromatic-stability index

Abstract

The $\chi$-stability index ${\mathrm{es}}_{\chi }(G)$ of a graph $G$ is the minimum number of its edges whose removal results in a graph with the chromatic number smaller than that of $G$. In this paper three open problems from [European J.\ Combin.\ 84 (2020) 103042] are considered. Examples are constructed which demonstrate that a known characterization of $k$-regular ($k\le 5$) graphs $G$ with ${\mathrm{es}}_{\chi }(G)=1$ does not extend to $k\ge 6$. Graphs $G$ with $\chi (G)=3$ for which ${\mathrm{es}}_{\chi }(G)+{\mathrm{es}}_{\chi }(\overline{G})=2$ holds are characterized. Necessary conditions on graphs $G$ which attain a known upper bound on ${\mathrm{es}}_{\chi }(G)$ in terms of the order and the chromatic number of $G$ are derived. The conditions are proved to be sufficient when $n\equiv 2(\mathrm{mod}3)$ and $\chi (G)=3$.