MAXIMUM ACHROMATIC NUMBER

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: A complete coloring of G, i.e., a partition of V into disjoint sets $V_1,V_2,\ldots,V_k$ such that each $V_i$ is an independent set for G and such that, for each pair of distinct sets $V_i$, $V_j$, $V_i\cup V_j$ is not an independent set.
• MEASURE: Cardinality of the complete coloring, i.e., the number of disjoint independent sets $V_i$.

  
  

• Good News: Approximable within $O(\vert V\vert/\sqrt{\log\vert V\vert})$ [100].
• Comment: Approximable within $O(\sqrt{\vert V\vert})$ for graphs of girth (length of shortest cycle) at least 6 [100].
• Garey and Johnson: GT5