More About Subcolorings

A subcoloring is a vertex coloring of a graph in which every color class induces a disjoint union of cliques. We derive a number of results on the combinatorics, the algorithmics, and the complexity of subcolorings. On the negative side, we prove that 2-subcoloring is NP-hard for comparability graphs, and that 3-subcoloring is NP-hard for AT-free graphs and for complements of planar graphs. On the positive side, we derive polynomial time algorithms for 2-subcoloring of complements of planar graphs, and for r-subcoloring of interval and of permutation graphs. Moreover, we prove asymptotically best possible upper bounds on the subchromatic number of interval graphs, chordal graphs, and permutation graphs in terms of the number of vertices. Received June 11, 2002; revised September 13, 2002 Published online: November 25, 2002 RID="*" ID="*" The work of HJB and FVF is sponsored by NWO-grant 047.008.006. FVF acknowledges support by EC contract IST-1999-14186, Project ALCOM-FT (Algorithms and Complexity – Future Technologies). Part of this work was done while FVF was visiting the University of Twente, and while he was a visiting postdoc at DIMATIA-ITI (supported by GAČR 201/99/0242 and by the Ministry of Education of the Czech Republic as project LN00A056). JN acknowledges support of ITI – the Project LN00A056 of the Czech Ministery of Education. GJW acknowledges support by the START program Y43-MAT of the Austrian Ministry of Science.