Premium
Ring graphs and Goldberg's bound on chromatic index
Author(s) -
Cao Yan,
Chen Guantao,
He Shushan,
Jing Guangming
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22494
Subject(s) - combinatorics , mathematics , conjecture , edge coloring , bipartite graph , chromatic scale , index (typography) , collatz conjecture , graph , discrete mathematics , multigraph , critical graph , line graph , graph power , computer science , world wide web
Let G be a multigraph with maximum degree Δ and chromatic index χ ′ . If G is bipartite then χ ′ = Δ . Otherwise, by a theorem of Goldberg, χ ′ ≤ Δ + 1 + ⌊ ( Δ − 2 ) / ( g o − 1 ) ⌋ , where g o denotes the odd girth of G . Stiebitz, Scheide, Toft, and Favrholdt in their book conjectured that if χ ′ = Δ + 1 + ⌊ ( Δ − 2 ) / ( g o − 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 g o = 3 . Stiebitz et al verified the conjecture for graphs with g o = 5 and Δ ≥ 10 . McDonald proved the conjecture when Δ − 2 is divisible by g o − 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 g o ≥ 3 with Δ ≥ ( g o 2 − 2 g o + 5 ) / 2 , and the maximum degree condition is best possible. This positive result leans on the positive resolution of the Goldberg‐Seymour conjecture.