Misra & Gries edge coloring algorithm

The Misra & Gries edge coloring algorithm is a <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> algorithm in <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a> that finds an <a href="/facts/Edge_coloring/AcdpUxCv">edge coloring</a> of any simple graph. The coloring produced uses at most 
 
 
 
 Δ
 +
 1
 
 
 {\displaystyle \Delta +1}
 
 colors, where 
 
 
 
 Δ
 
 
 {\displaystyle \Delta }
 
 is the maximum <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> of the graph. This is optimal for some graphs, and it uses at most one color more than optimal for all others. The existence of such a coloring is guaranteed by <a href="/facts/Vizing%27s_theorem/hHtEtK9t">Vizing's theorem</a>.
It was first published by <a href="/facts/Jayadev_Misra/nfgR4Lw3">Jayadev Misra</a> and <a href="/facts/David_Gries/36zCYJT8">David Gries</a> in 1992. It is a simplification of a prior algorithm by <a href="/facts/B%C3%A9la_Bollob%C3%A1s/9T1eot5o">Béla Bollobás</a>.
This algorithm is the fastest known almost-optimal algorithm for edge coloring, executing in 
 
 
 
 O
 (
 
 |
 
 E
 
 |
 
 
 |
 
 V
 
 |
 
 )
 
 
 {\displaystyle O(|E||V|)}
 
 time. A faster time bound of 
 
 
 
 O
 
 (
 
 
 |
 
 E
 
 |
 
 
 
 
 |
 
 V
 
 |
 
 log
 ⁡
 
 |
 
 V
 
 |
 
 
 
 
 )
 
 
 
 {\displaystyle O\left(|E|{\sqrt {|V|\log |V|}}\right)}
 
 was claimed in a 1985 technical report by Gabow et al., but this has never been published.
In general, optimal edge coloring is NP-complete, so it is very unlikely that a polynomial time algorithm exists. There are however exponential time <a href="/facts/Edge_coloring/AcdpUxCv">exact edge coloring algorithms</a> that give an optimal solution.

Misra & Gries edge coloring algorithm open-in-new

Misra & Gries edge coloring algorithm