In a graph coloring, each color class induces a disjoint union of isolated vertices. A graph subcoloring generalizes this concept, since here each color class induces a disjoint union of complete graphs. Erdős and independently Albertson et al. proved that every graph of maximum degree at most 3 has a 2-subcoloring.We point out in this paper that this fact is best possible with respect to degree-constraints by showing that the problem of recognizing 2-subcolorable graphs with maximum degree 4 is NP-complete, even when restricted to triangle-free planar graphs. Moreover, in general, for fixed k, recognizing k-subcolorable graphs is NP-complete on graphs with maximum degree at most k ². In contrast, we show that, for arbitrary k, k-SUBCOLORABILITY can be computed efficiently on graphs of bounded treewidth and on cographs.