Precoloring with cliques and stable sets in cographs

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.


    • ROSE-REPORT-2006-006

    Record created on 2006-09-27, modified on 2016-08-08


  • There is no available fulltext. Please contact the lab or the authors.

Related material