Abstract
Let G be a multigraph with maximum degree Δ and chromatic index χ′. If G is bipartite then χ′ = Δ. Otherwise, by a theorem of Goldberg, χ′ ≤ Δ + 1 + ⌊(Δ − 2)/(go − 1)⌋, where go denotes the odd girth of G. Stiebitz, Scheide, Toft, and Favrholdt in their book conjectured that if χ′ = Δ + 1 + ⌊(Δ − 2)/(go − 1)⌋ then G contains as a subgraph a ring graph R with the same chromatic index. Vizing's characterization of graphs with chromatic index attaining the Shannon's bound showed the above conjecture holds for go = 3. Stiebitz et al verified the conjecture for graphs with go = 5 and Δ ≥ 10. McDonald proved the conjecture when Δ − 2 is divisible by go − 1. In this paper, we show that the chromatic index condition alone is not sufficient to give the conclusion in the conjecture. On the positive side, we show that the conjecture holds for every go ≥ 3 with Δ ≥ (go − 2go + 5)/2, and the maximum degree condition is best possible. This positive result leans on the positive resolution of the Goldberg-Seymour conjecture.
Original language | English (US) |
---|---|
Pages (from-to) | 440-449 |
Number of pages | 10 |
Journal | Journal of Graph Theory |
Volume | 93 |
Issue number | 3 |
DOIs | |
State | Published - Mar 1 2020 |
Externally published | Yes |
Keywords
- chromatic index
- critical chromatic graph
- maximum degree
- odd girth
ASJC Scopus subject areas
- Geometry and Topology
- Discrete Mathematics and Combinatorics