Improved bounds for the chromatic index of graphs and multigraphs
S. L. Hakimi, Edward F. Schmeichel · Journal of Graph Theory · 1999
We show that coloring the edges of a multigraph G in a particular order often leads to improved upper bounds for the chromatic index χ′(G). Applying this to simple graphs, we significantly generalize recent conditions based on the core of G 〈i.e., the subgraph of G induced by the vertices of degree Δ(G)〉, which insure that χ′(G) = Δ(G). Finally, we show that in any multigraph G in which every cycle of length larger than 2 contains a simple edge, where μ(G) is the largest edge multiplicity in G. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 311–326, 1999