2020/07/30 by Shenwei Huang, Sandi Klavžar, Huang, Shenwei +7
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2007.15368
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≤ 5) graphs G with \rm esχ(G) = 1 does not extend to k≥ 6. Graphs G with χ(G)=3 for which \rm esχ(G)+\rm esχ(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≡ 2 \pmod 3 and χ(G)=3.