On the chromatic edge stability index of graphs

Please enable javascript in your browser.

This page was sent successfuly

Bookmark

876 viewed

Akbari, S

876 Viewed

Type of Document: Article
DOI: 10.1016/j.ejc.2023.103690
Publisher: Academic Press , 2023
Abstract:
Given a non-trivial graph G, the minimum cardinality of a set of edges F in G such that χ′(G∖F)<χ′(G) is called the chromatic edge stability index of G, denoted by esχ(G), and such a (smallest) set F is called a (minimum) mitigating set. While 1≤esχ(G)≤⌊n/2⌋ holds for any graph G, we investigate the graphs with extremal and near-extremal values of esχ(G). The graphs G with esχ(G)=⌊n/2⌋ are classified, and the graphs G with esχ(G)=⌊n/2⌋−1 and χ′(G)=Δ(G)+1 are characterized. We establish that the odd cycles and K2 are exactly the regular connected graphs with the chromatic edge stability index 1; on the other hand, we prove that it is NP-hard to verify whether a graph G has esχ(G)=1. We also prove that every minimum mitigating set of an r-regular graph G, where r≠4, with esχ(G)=2 is a matching. Furthermore, we propose a conjecture that for every graph G there exists a minimum mitigating set, which is a matching, and prove that the conjecture holds for graphs G with esχ(G)∈{1,2,⌊n/2⌋−1,⌊n/2⌋}, and for bipartite graphs. © 2023
Keywords:
Source: European Journal of Combinatorics ; Volume 111 , 2023 ; 01956698 (ISSN)
URL: https://www.sciencedirect.com/science/article/pii/S0195669823000070