Approximating the chromatic index of multigraphs
by
Xingxing Yu
School of Mathematics, Georgia Tech
Coauthors: Guantao Chen & Wenan Zang

It is well known that if G is a multigraph then c'(G) ≥ c'^*(G):=max{D(G), G(G)}, where c'(G) is the chromatic index of G, c'^*(G) is the fractional chromatic index of G, D(G) is the maximum degree of G, and G(G)=max{2|E(G[U])|/(|U|-1): U ⊆ V(G), |U| ≥ 3,  |U| is odd}. The conjecture that c'(G) ≤ max{D(G)+1, ⌈G(G)⌉} was made independently by Goldberg (1973), Anderson (1977), and Seymour (1979). We prove this conjecture for multigraphs G with c'(G) > ⌊D(G)+√{D(G)/2}⌋.

Date received: April 18, 2008