More About Subcolorings
More About Subcolorings
复制标题
有关底色的更多信息
DOI：
10.1007/s00607-002-1461-1
复制
发表时间：
2002
期刊：
影响因子：
3.7
通讯作者：
G. Woeginger
中科院分区：
文献类型：
--
作者：
H. Broersma;F. Fomin;J. Nesetril;G. Woeginger
亚颜色是图形的顶点着色，其中每个颜色类都会诱导群集的不相交。我们得出了有关组合学，算法和子颜色的复杂性的许多结果。在负面的一面，我们证明2-填充是可比性图的NP-固定，并且3 subcoloring是AT-的NP-HARD。免费图形和用于平面图的补充。在正面，我们得出了多项式时间算法，用于2个平面图补充，以及间隔和置换图的r-划分。此外，我们证明了根据顶点的数量，在间隔图，弦图和串联图的渐近数，弦图和置换图上渐近上最好的上限。
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.