A partition of the vertices of a graph G into k pairwise disjoint sets V-1,
..., V-k is called an (r(l),..., r(k))-subcoloring if the subgraph Gi of G
induced by Vi, 1 less than or equal to i less than or equal to k, consists
of disjoint complete subgraphs. each of which has cardinality no more than
ri. Due to Erdos and Albertson et al., independently, every cubic (i.e., 3-
regular) graph has a (2,2)-subcoloring. Albertson et al. then asked for cub
ic graphs having (1, 2)-subcolorings. We point out in this paper that this
question is algorithmically difficult by showing that recognizing (1, 2)-su
bcolorable cubic graphs is NP-complete, even when restricted to triangle-fr
ee planar graphs. (C) 2002 Elsevier Science B.V. All rights reserved.