Graph Subcolorings: Complexity and Algorithms
Graph Subcolorings: Complexity and Algorithms
复制标题
图的子着色：复杂性和算法
DOI：
10.1007/3-540-45477-2_15
复制
发表时间：
2001
期刊：
影响因子：
2.3
通讯作者：
Eike Seidel
中科院分区：
文献类型：
--
作者：
J. Fiala;K. Jansen;V. B. Le;Eike Seidel
在图形着色中，每个颜色类都会引起孤立顶点的不相交。图表子颜色概括了这个概念，因为这里每个颜色类都会引起完整图的不相交联合。 Erd？OS和Albertson等人。证明最多3的每个最高度图都具有2个覆盖。我们在本文中指出，对于程度约束，最好通过表明识别最高度4的2个可掩盖图的问题是NP完整的，即使仅限于无三角形的平面图，也是如此。此外，通常对于固定的K，识别可k-subcoloror的图是最高度k2的图形上的NP完整图。相比之下，我们表明，对于任意K，可以在有界的树宽和cographs上有效地计算k缩放性。
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. Erd?os and independently Albertson et al. proved that every graph of maximum degree at most 3 has a 2-subcoloring. We point out in this paper 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 computed efficiently on graphs of bounded treewidth and on cographs.