Abstract: The chromatic index chi'(G) of a graph G (multiple edges allowed) is the minimum number of colors needed to color the edges of G such that adjacent edges receive distinct colors. The edge coloring problem is NP-hard. There are two elementary lower bounds. Always chi'(G) >= D(G), where D(G) is the maximum degree of G. Also, chi'(G) >= W(G), where W(G) is the maximum, over all subgraphs H of G, of e(H)/\floor[n(H)/2].
Graphs with chi'(G)=W(G) are called elementary. Goldberg and Seymour independently conjectured in the 1970s that all graphs G with chi'(G) >= D(G)+2 are elementary. For an integer m, let Jm denote the class of all graphs G such that chi'(G) > (mD(G)+m-3)/(m-1). Shannon's Theorem implies that J3 is empty. Always Jm\subseteq Jm+1, and the union of all Jm with m >= 3 consists of all graphs G such that chi'(G) >= D(G)+2.
The conjecture has previously been proved for all graphs in Jm for odd m up to 11. We use an extension of the method Tashkinov used for m=11 to prove that every graph in J13 is elementary. The proof yields a polynomial-time algorithm to properly color the edges of every graph G with at most floor[(13chi'(G)+10)/12] colors.