Structural properties of edge-chromatic critical multigraphs

Guantao Chen, Guangming Jing

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


Let G be a graph with possible multiple edges but no loops. The density of G, denoted by ρ(G), is defined as [Formula presented]. Goldberg (1973) and Seymour (1974) independently conjectured that if the chromatic index χ(G) satisfies χ(G)≥Δ(G)+2 then χ(G)=ρ(G), which is commonly regarded as Goldberg's conjecture. An equivalent conjecture, usually credited to Jakobsen, states that for any odd integer m≥3, if [Formula presented]. The Tashkinov tree technique, a common generalization of Vizing fans and Kierstead paths for multigraphs, has emerged as the main tool to attack these two conjectures. On the other hand, Asplund and McDonald recently showed that there is a limitation to this method. In this paper, we will go beyond Tashkinov trees and provide a much larger extended structure, using which we see hope to tackle the conjecture. Applying this new technique, we show that the Goldberg's conjecture holds for graphs with Δ(G)≤39 or |V(G)|≤39 and the Jakobsen Conjecture holds for m≤39, where the previously known best bound is 23. We also improve a number of other related results.

Original languageEnglish (US)
Pages (from-to)128-162
Number of pages35
JournalJournal of Combinatorial Theory. Series B
StatePublished - Nov 2019
Externally publishedYes


  • Chromatic index
  • Critical chromatic graph
  • Graph density
  • Tashkinov tree

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Structural properties of edge-chromatic critical multigraphs'. Together they form a unique fingerprint.

Cite this