Some extremal results on the chromatic-stability index

The $χ$-stability index ${\rm es}_χ(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 ${\rm es}_χ(G) = 1$ does not extend to $k\ge 6$. Graphs $G$ with $χ(G)=3$ for which ${\rm es}_χ(G)+{\rm es}_χ(\overline{G}) = 2$ holds are characterized. Necessary conditions on graphs $G$ which attain a known upper bound on ${\rm es}_χ(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 \pmod 3$ and $χ(G)=3$.

No reviews yet.

No comments yet.