MINIMUM EDGE COLORING

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: A coloring of E, i.e., a partition of E into disjoint sets $E_1,E_2,\ldots,E_k$ such that, for $1\le i\le k$, no two edges in $E_i$ share a common endpoint in G.
• MEASURE: Cardinality of the coloring, i.e., the number of disjoint sets $E_i$.

  
  

• Good News: Approximable within 4/3, and even approximable with an absolute error guarantee of 1 [461].
• Bad News: Not approximable within 4/3$-\varepsilon$ for any $\varepsilon >0$ [258].
• Comment: Also called Minimum Chromatic Index. APX-intermediate unless the polynomial-hierarchy collapses [125]. On multigraphs the problem is approximable within 1.1 $+(0.8/\mbox{\sl opt})$ [387]. The maximization variation in which the input is extended with a positive integer k, and the problem is to find the maximum number of consistent vertices over all edge-colorings with k colors, is approximable within e/(e-1) [80], but does not admit a PTAS [400].
• Garey and Johnson: OPEN5