2003/01/01 by Jiřı́ Fiala, Klaus Jansen, Van Bang Lê +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Combinatorics #Mathematics #Cograph #Discrete mathematics #Treewidth #Pathwidth #1-planar graph #Chordal graph #Split graph #Indifference graph #Planar graph #Clique-sum #Degree (music) #Partial k-tree #Bounded function #Graph #Line graph
paper · doi:10.1137/s0895480101395245
openalex publication_date 2003/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
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).