Accepted author manuscript, 245 KB, PDF document
Available under license: CC BY: Creative Commons Attribution 4.0 International License
Final published version
Licence: CC BY: Creative Commons Attribution 4.0 International License
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Article number | 113850 |
---|---|
<mark>Journal publication date</mark> | 30/04/2024 |
<mark>Journal</mark> | Discrete Mathematics |
Issue number | 4 |
Volume | 347 |
Publication Status | Published |
Early online date | 21/12/23 |
<mark>Original language</mark> | English |
The chromatic edge stability index es χ ′ (G) of a graph G is the minimum number of edges whose removal results in a graph with smaller chromatic index. We give best-possible upper bounds on es χ ′ (G) in terms of the number of vertices of degree Δ(G) (if G is Class 2), and the numbers of vertices of degree Δ(G) and Δ(G)−1 (if G is Class 1). If G is bipartite we give an exact expression for es χ ′ (G) involving the maximum size of a matching in the subgraph induced by the vertices of degree Δ(G). Finally, we consider whether a minimum mitigating set, that is a set of size es χ ′ (G) whose removal reduces the chromatic index, has the property that every edge meets a vertex of degree at least Δ(G)−1; we prove that this is true for some minimum mitigating set of G, but not necessarily for every minimum mitigating set of G.