The edge coloring problem is the optimization problem of finding an edge coloring of a graph that uses as few colors as possible (Cao et al. 2019). An optimal solution is a minimum edge coloring, and the optimum value is the edge chromatic number.
The associated decision version takes a graph 
and a positive integer 
and asks whether 
has an edge coloring using
at most 
colors, equivalently whether 
. This decision problem is an NP-complete
problem even when 
is a cubic graph and 
(Holyer 1981). Consequently, the optimization problem is
an NP-hard problem.
The edge coloring problem on a graph 
is equivalent to the vertex
coloring problem on its line graph 
. An edge coloring of 
is a vertex
coloring of 
(Skiena 1990, p. 216). Polyhedral formulations provide another exact approach
(Nemhauser and Park 1991).
