Time complexity analysis of RLS and (1 + 1) EA for the edge coloring problem
Jakob Bossek, Dirk Sudholt · 2019
The edge coloring problem asks for an assignment of colors to edges of a graph such that no two incident edges share the same color and the number of colors is minimized. It is known that all graphs with maximum degree Δ can be colored with Δ or Δ + 1 colors, but it is NP-hard to determine whether Δ colors are sufficient.