2021/09/15 by Yan Cao, Guantao Chen, Cao, Yan +3
Computer Science · Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.2109.07610
arxiv created 2021/09/15 · openalex publication_date 2021/09/15 · arxiv updated 2021/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.