The NP-completeness of (1,r)-subcolorability of cubic graphs

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.