Next: MINIMUM EDGE COLORING Up: Covering and Partitioning Previous: MINIMUM GRAPH COLORING Index

### MAXIMUM ACHROMATIC NUMBER

- INSTANCE: Graph .
- SOLUTION: A complete coloring of G, i.e., a partition of V into disjoint sets such that each Vi is an independent set for G and such that, for each pair of distinct sets Vi, Vj, is not an independent set.

- MEASURE: Cardinality of the complete coloring, i.e., the number of disjoint independent sets Vi.

- Good News: Approximable within [92].
- Comment: Approximable within for graphs of girth (length of shortest cycle) at least 6 [92].

- Garey and Johnson: GT5