# ILP for minimum edge coloring problem

We know that for a graph $G=(V,E)$, minimum edge coloring is a coloring of $E$, i.e., a partition of $E$ into disjoint sets $E_1, E_2, \dots, E_k$ such that, for $1 \leq i \leq k$, no two edges in $E_i$ share a common endpoint in $G$. Now how can we write an Integer linear program (ILP) to solve the minimum edge coloring problem?

If $c$ is an upper bound for the number of colours (in case of doubt use $|E|$), then you could use binary assigment variables $x_{ie}$ for assigning colour $i$ to edge $e$. Then, for every two edges $e,f$ which share a node one can introduce a constraint $x_{ie} + x_{if} \leq 1$. Furthermore one introduces binary variables $z_i$ stating if colour $i$ is used and relates them to $x$ by $x_{ie} \leq z_i$. After that you try to minimize the sum of the $z_i$.
In particular, you have a variable $x_M$ for every (maximal) matching $M$, and you require that $$\sum_{M \ni e} x_M \ge 1$$ for every edge $e$ in your graph. You then minimize the sum of the $x_M$.