Abstract
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 language | English (US) |
---|---|
Pages (from-to) | 128-162 |
Number of pages | 35 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 139 |
DOIs | |
State | Published - Nov 2019 |
Externally published | Yes |
Keywords
- Chromatic index
- Critical chromatic graph
- Graph density
- Tashkinov tree
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics