2021/08/30 by Akbari, Saieed, Beikmohammadi, Arash, Klavžar, Sandi +1 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2108.12994
The chromatic vertex (resp. edge) stability number \rm vsχ(G) (resp. \rm esχ(G)) of a graph G is the minimum number of vertices (resp. edges) whose deletion results in a graph H with χ(H)=χ(G)-1. In the main result it is proved that if G is a graph with χ(G) ∈ \ Δ(G), Δ(G)+1 \, then \rm vsχ(G) = \rm ivsχ(G), where \rm ivsχ(G) is the independent chromatic vertex stability number. The result need not hold for graphs G with χ(G) ≤ (Δ(G)+1)/(2). It is proved that if χ(G) > (Δ(G))/(2)+1, then \rm vsχ(G) = \rm esχ(G). A Nordhaus-Gaddum-type result on the chromatic vertex stability number is also given.