Skip to main content

Research Repository

Advanced Search

More about subcolorings

Broersma, H.J.; Fomin, F.V.; Nesetril, J.; Woeginger, G.J.

Authors

H.J. Broersma

F.V. Fomin

J. Nesetril

G.J. Woeginger



Abstract

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.

Citation

Broersma, H., Fomin, F., Nesetril, J., & Woeginger, G. (2002). More about subcolorings. Computing, 69(3), 187-203. https://doi.org/10.1007/s00607-002-1461-1

Journal Article Type Article
Publication Date 2002-11
Deposit Date Apr 23, 2008
Journal Computing
Print ISSN 0010-485X
Electronic ISSN 1436-5057
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 69
Issue 3
Pages 187-203
DOI https://doi.org/10.1007/s00607-002-1461-1
Keywords Graph coloring, Special graph classes, Polynomial time algorithm, Computational complexity.

You might also like



Downloadable Citations