3
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

There is a well known integer program for coloring vertices, and so you can use the same idea for coloring edges.

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

The edges and matchings here are analogous to vertices and independent sets in the program for vertex coloring. Another way of looking at things is that this is just the vertex coloring IP applied to the line graph of the graph in question.

Note that the LP relaxation of the vertex coloring IP gives the fractional chromatic number, which remains NP-hard to compute. However the LP relaxation of this IP for edge coloring gives the fractional chromatic index which is polynomial time computable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.