No Detail Found!

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

Author(s)
Martin Knor Slovak University of Technology in Bratislava,Bratislava,Slovakia
Mirko Petrusˇevski Faculty of Mechanical Engineering, University Ss. Cyril and Methodius in Skopje,Skopje,Macedonia
Riste Sˇ krekovski Faculty of Information Studies,Novo Mesto,Slovenia; Faculty of Mathematics and Physics, University of Ljubljana,Ljubljana,Slovenia
Abstract
The (independent) chromatic vertex stability (ivs (G)) vs (G) is the minimum size of (independent) set S V (G) such that (G S) = (G) 1. The question of how large must the chromatic number (G) of a graph G be, in terms of the maximum degree (G), to ensure the equality ivs (G) = vs (G) was raised by Akbari et al. [European J. Combin. 102 (2022) #103504]; the authors showed that ivs (G) = vs (G) if (G) 2 f (G); (G) + 1g, 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.
Publication Details
Page(s) 75-80
Published Journal: Discrete Mathematics Letters, Volume: 10, Issue: 0, Year: 2022

Request the full text from PASTIC

Keywords
maximum degree, chromatic number, chromatic vertex stability, independent chromatic vertex stability
0

Citations

0

Downloads

115

Views