Home > Research > Publications & Outputs > Tight Bounds on the Chromatic Edge Stability In...

Associated organisational unit

Electronic data

  • ChromaticEdgeStabilityIndex

    Accepted author manuscript, 245 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

Text available via DOI:

View graph of relations

Tight Bounds on the Chromatic Edge Stability Index of Graphs

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published
Close
Article number113850
<mark>Journal publication date</mark>30/04/2024
<mark>Journal</mark>Discrete Mathematics
Issue number4
Volume347
Publication StatusPublished
Early online date21/12/23
<mark>Original language</mark>English

Abstract

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.