Publication
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.
Serge Vaudenay, Bénédikt Minh Dang Tran
Maryam Kamgarpour, Tony Alan Wood
Oliver Kröcher, Frédéric Vogel, David Baudouin, Ayush Agarwal