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?



ILP for 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$.


