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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom