GT6 M AXIMUM A CHROMATIC N UMBER

     
• I NSTANCE : Graph .
• S OLUTION : A complete coloring of G , i.e., a partition of V into disjoint sets such that each is an independent set for G and such that, for each pair of distinct sets , , is not an independent set.
• M EASURE : Cardinality of the complete coloring, i.e., the number of disjoint independent sets .

• Good News: Approximable within [ 64 ].
• Comment: Approximable within for graphs of girth (length of shortest cycle) at least 6 [ 64 ].
• Garey and Johnson: GT5