More about subcolorings

Haitze J. Broersma, F.V. Fomin, J. Nesetril, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

15 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)187-203
Number of pages7
JournalComputing
Volume69
Issue number3
DOIs
Publication statusPublished - 2002

Keywords

  • METIS-208148

Fingerprint Dive into the research topics of 'More about subcolorings'. Together they form a unique fingerprint.

Cite this