Structural properties of edge-chromatic critical multigraphs

摘要

Let G be a graph with possible multiple edges but no loops. The density of G, denoted by rho(G) , is defined as max(H subset of G, vertical bar V(H)vertical bar >= 2) inverted right perpendicular vertical bar E(H)vertical bar/left perpendicular vertical bar V(H)vertical bar/2 right perpendicular inverted left perpendicular. Goldberg (1973) and Seymour (1974) independently conjectured that if the chromatic index chi'(G) satisfies chi'(G) >= Delta(G) + 2 then chi'(G) = rho(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 chi'(G) >= m Delta(G)/m-1 + m-3/m-1 then chi'(G) = rho(G). 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 Delta(G) <= 39, or vertical bar V(G)vertical bar <= 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. (C) 2019 Elsevier Inc. All rights reserved.