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).