TY - GEN
T1 - More about subcolorings
AU - Broersma, H.J.
AU - Fomin, F.V.
AU - Nešetril, J.
AU - Woeginger, G.J.
PY - 2002
Y1 - 2002
N2 - 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.
AB - 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.
U2 - 10.1007/3-540-36379-3_7
DO - 10.1007/3-540-36379-3_7
M3 - Conference contribution
SN - 978-3-540-00331-1
T3 - Lecture Notes in Computer Science
SP - 68
EP - 79
BT - Proceedings of the 28th Workshop on Graph-Theoretic Concepts in Computer Science (WG'02, Cseky Krumlov, Czech Republic, June 13-15, 2002)
PB - Springer
CY - Berlin
ER -