We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

More about subcolorings.

Broersma, H. J. and Fomin, F. V. and Nešetřil, J. and Woeginger, G. J. (2002) 'More about subcolorings.', Computing., 69 (3). pp. 187-203.


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.

Item Type:Article
Keywords:Graph coloring, Special graph classes, Polynomial time algorithm, Computational complexity.
Full text:Full text not available from this repository.
Publisher Web site:
Record Created:23 Apr 2008
Last Modified:08 Apr 2009 16:22

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Look up in GoogleScholar | Find in a UK Library