Premium
A note on Goldberg's conjecture on total chromatic numbers
Author(s) -
Cao Yan,
Chen Guantao,
Jing Guangming
Publication year - 2022
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.22771
Subject(s) - multigraph , conjecture , combinatorics , edge coloring , mathematics , chromatic scale , critical graph , multiplicity (mathematics) , graph , brooks' theorem , discrete mathematics , chordal graph , graph power , 1 planar graph , line graph , geometry
Let G = ( V ( G ) , E ( G ) ) be a multigraph with maximum degree Δ ( G ) , chromatic index χ ′ ( G ) , and total chromatic number χ ″ ( G ) . The total coloring conjecture proposed by Behzad and Vizing, independently, states that χ ″ ( G ) ≤ Δ ( G ) + μ ( G ) + 1 for a multigraph G , where μ ( G ) is the multiplicity of G . Moreover, Goldberg conjectured that χ ″ ( G ) = χ ′ ( G ) if χ ′ ( G ) ≥ Δ ( G ) + 3 and noticed the conjecture holds when G is an edge‐chromatic critical graph. By assuming the Goldberg–Seymour conjecture, we show that χ ″ ( G ) = χ ′ ( G ) if χ ′ ( G ) ≥ max { Δ ( G ) + 2 , ∣ V ( G ) ∣ + 1 } in this note. Consequently, χ ″ ( G ) = χ ′ ( G ) if χ ′ ( G ) ≥ Δ ( G ) + 2 and G has a spanning edge‐chromatic critical subgraph.