On Chromatic Vertex Stability of 3-Chromatic Graphs With Maximum Degree 4
Martin Knor, Mirko Petruševski, Riste Škrekovski · Discrete Mathematics Letters · 2022
The (independent) chromatic vertex stability (ivsχ(G)) vsχ(G) is the minimum size of (independent, and also pointed out to graphs with χ(G) ≤ (∆(G) + 1)/2 for which ivsχ(G) > vsχ(G).In the light of their findings, they raised the following problem: Is it true that χ(G) ≥ ∆(G)/2 + 1 always implies ivsχ(G) = vsχ(G)?This threshold question was recently answered in the negative by Cambrie et al. [arXiv: 2203.13833v1,(2022)].In this paper, we show that the smallest instance for counterexamples is the case (χ(G), ∆(G)) = (3, 4), with the smallest possible order being 9 (and there are 30 such graphs).We construct exponentially many graphs G having ∆(G) = 4, χ(G) = 3, ivsχ(G) = 3, and vsχ(G) = 2.