On chromatic vertex stability of 3-chromatic graphs with maximum degree 4

Abstract

The (independent) chromatic vertex stability ($\ivs(G)$) $\vs(G)$ is the minimum size of (independent) set $S\subseteq V(G)$ such that $\chi (G-S)=\chi (G)-1$. In this paper we construct infinitely many graphs $G$ with $\Delta (G)=4$, $\chi (G)=3$, $\ivs(G)=3$ and $\vs(G)=2$, which gives a partial negative answer to a problem posed in \cite{ABKM}.

7 pages, 4 figures