GT7 M INIMUM E DGE C OLORING

     
• I NSTANCE : Graph .
• S OLUTION : A coloring of E , i.e., a partition of E into disjoint sets such that, for , no two edges in share a common endpoint in G .
• M EASURE : Cardinality of the coloring, i.e., the number of disjoint sets .

• Good News: Approximable within 4/3, and even approximable with an absolute error guarantee of 1 [ 340 ].
• Bad News: Not approximable within 4/3 for any [ 175 ].
• Comment: Also called Minimum Chromatic Index .     A PX -intermediate unless the polynomial-hierarchy collapses [ 85 ]. On multigraphs the problem is approximable within 1.1 [ 279 ]. 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) [ 52 ], but does not admit a PTAS [ 290 ].
• Garey and Johnson: OPEN5