Tight Bounds on the Chromatic Edge Stability Index of Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909091496984576 |
|---|---|
| author | Akbari, Saieed Haslegrave, John Javadi, Mehrbod Nahvi, Nasim Niaparast, Helia |
| author_facet | Akbari, Saieed Haslegrave, John Javadi, Mehrbod Nahvi, Nasim Niaparast, Helia |
| contents | The chromatic edge stability index $\mathrm{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 $\mathrm{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 $\mathrm{es}_{χ'}(G)$ involving the maximum size of a matching in the subgraph induced by vertices of degree $Δ(G)$. Finally, we consider whether a minimum mitigating set, that is a set of size $\mathrm{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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_03953 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Tight Bounds on the Chromatic Edge Stability Index of Graphs Akbari, Saieed Haslegrave, John Javadi, Mehrbod Nahvi, Nasim Niaparast, Helia Combinatorics 05C15, 05C70 The chromatic edge stability index $\mathrm{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 $\mathrm{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 $\mathrm{es}_{χ'}(G)$ involving the maximum size of a matching in the subgraph induced by vertices of degree $Δ(G)$. Finally, we consider whether a minimum mitigating set, that is a set of size $\mathrm{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$. |
| title | Tight Bounds on the Chromatic Edge Stability Index of Graphs |
| topic | Combinatorics 05C15, 05C70 |
| url | https://arxiv.org/abs/2206.03953 |