Abstract
Precoloring extension problems are known to be NP-complete in several classes of graphs. Here, we consider precolorings of cographs with not only stable sets but also with cliques. We give polynomial time algorithms to extend such a precoloring in an optimal way according to several objective functions.
Details
Title
Precoloring with cliques and stable sets in cographs
Author(s)
Demange, Marc ; Ekim, Tinaz
Date
2006
Laboratories
ROSE
Record Appears in
Scientific production and competences > SB - School of Basic Sciences > SB Archives > ROSE - Chair of Operations Research SE
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Work produced at EPFL
Technical Reports
Published
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Work produced at EPFL
Technical Reports
Published
Record creation date
2006-09-27