Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.23274 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912863224856576 |
|---|---|
| author | Chen, Guantao Fiujlaali, Alireza Johnsen-Yu, Anna McDonald, Jessica |
| author_facet | Chen, Guantao Fiujlaali, Alireza Johnsen-Yu, Anna McDonald, Jessica |
| contents | Vizing and Gupta showed that the chromatic index $χ'(G)$ of a graph $G$ is bounded above by $Δ(G) + μ(G)$, where $Δ(G)$ and $μ(G)$ denote the maximum degree and the maximum multiplicity of $G$, respectively. Steffen refined this bound, proving that $χ'(G) \leq Δ(G) + \left\lceil μ(G)/\left\lfloor g(G)/2 \right\rfloor \right\rceil$, where $g(G)$ is the girth of the graph $G$. A {\it ring graph} is a graph obtained from a cycle by duplicating some edges. The equality in Steffen's bound is achieved by ring graphs of the form $μC_g$, obtained from an odd cycle $C_g$ by duplicating each edge $μ$ times. We answer two questions posed by Stiebitz et al. regarding the characterization of graphs which achieve Steffen's bound. In particular, we show that if $G$ is a critical graph which achieves Steffen's bound with $g(G)\geq 5$ and $χ'(G)\geq Δ+2$, then $G$ must be a ring graph of odd girth. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_23274 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On graphs with girth at least five achieving Steffen's edge coloring bound Chen, Guantao Fiujlaali, Alireza Johnsen-Yu, Anna McDonald, Jessica Combinatorics Vizing and Gupta showed that the chromatic index $χ'(G)$ of a graph $G$ is bounded above by $Δ(G) + μ(G)$, where $Δ(G)$ and $μ(G)$ denote the maximum degree and the maximum multiplicity of $G$, respectively. Steffen refined this bound, proving that $χ'(G) \leq Δ(G) + \left\lceil μ(G)/\left\lfloor g(G)/2 \right\rfloor \right\rceil$, where $g(G)$ is the girth of the graph $G$. A {\it ring graph} is a graph obtained from a cycle by duplicating some edges. The equality in Steffen's bound is achieved by ring graphs of the form $μC_g$, obtained from an odd cycle $C_g$ by duplicating each edge $μ$ times. We answer two questions posed by Stiebitz et al. regarding the characterization of graphs which achieve Steffen's bound. In particular, we show that if $G$ is a critical graph which achieves Steffen's bound with $g(G)\geq 5$ and $χ'(G)\geq Δ+2$, then $G$ must be a ring graph of odd girth. |
| title | On graphs with girth at least five achieving Steffen's edge coloring bound |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2601.23274 |