On graphs with girth at least five achieving Steffen's edge coloring bound
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 $μ$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.23274
curl -X POST /api/v1/records/arxiv/2601.23274/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.23274/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'