Title: Graph Subcolorings: Complexity and Algorithms
Abstract: 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. Erdos and, independently, Albertson et al., proved that every graph of maximum degree at most 3 has a 2-subcoloring. We point out 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 k2 . In contrast, we show that, for arbitrary k, k-SUBCOLORABILITY can be decided in linear time on graphs with bounded treewidth and on graphs with bounded cliquewidth (including cographs as a specific case).
Publication Year: 2003
Publication Date: 2003-01-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 24
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot