Next: MINIMUM FEEDBACK VERTEX SET
Up: Covering and Partitioning
Previous: MAXIMUM ACHROMATIC NUMBER
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.
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 .
- Bad News:
Not approximable within 4/3
Also called Minimum Chromatic Index.
APX-intermediate unless the polynomial-hierarchy collapses
On multigraphs the problem is approximable within 1.1
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) , but does not admit a PTAS .
- Garey and Johnson: OPEN5