Subcoloring

In graph theory, a subcoloring is an assignment of colors to a graph's vertices such that each color class induces a vertex disjoint union of cliques.

That is, each color class should form a cluster graph.

The subchromatic number χS(G) of a graph G is the fewest colors needed in any subcoloring of G. Subcoloring and subchromatic number were introduced by Albertson et al. (1989).

More specifically, the problem of determining whether a planar graph has subchromatic number at most 2 is NP-complete, even if it is a The subchromatic number of a cograph can be computed in polynomial time (Fiala et al. 2003).

For every fixed integer r, it is possible to decide in polynomial time whether the subchromatic number of interval and permutation graphs is at most r (Broersma et al. 2002).