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.


Year:
2006
Laboratories:




 Record created 2006-09-27, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)