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
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Tight Bounds on the Chromatic Edge Stability Index of Graphs
AU - Akbari, Saieed
AU - Haslegrave, John
AU - Javadi, Mehrbod
AU - Nahvi, Nasim
AU - Niaparast, Helia
PY - 2024/4/30
Y1 - 2024/4/30
N2 - 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.
AB - 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.
KW - Edge coloring
KW - Chromatic index
KW - Chromatic edge stability index
U2 - 10.1016/j.disc.2023.113850
DO - 10.1016/j.disc.2023.113850
M3 - Journal article
VL - 347
JO - Discrete Mathematics
JF - Discrete Mathematics
SN - 0012-365X
IS - 4
M1 - 113850
ER -