Monopolar graphs: Complexity of computing classical graph parameters.

A graph G = (V , E) is monopolar if V can be partitioned into a stable set and a set inducing the union of vertex-disjoint cliques. Motivated by an application of the clique partitioning problem on monopolar graphs to the cosmetic manufacturing, we study the complexity of computing classical graph parameters on the class of monopolar graphs. We show that computing the clique partitioning, stability and chromatic numbers of monopolar graphs is NP -hard. Conversely, we prove that every monopolar graph has a polynomial number of maximal cliques thus obtaining that a maximum-weight clique can be found in polynomial time on monopolar graphs. [ABSTRACT FROM AUTHOR]