Precoloring Extension on Chordal Graphs
Dániel Marx · Birkhäuser Basel eBooks · 2006
In the precoloring extension problem ( PrExt ) we are given a graph with some of the vertices having preassigned colors and it has to be decided whether this coloring can be extended to a proper κ -coloring of the whole graph. 1- PrExt is the special case where every color is assigned to at most one vertex in the precoloring. Answering an open question of Hujter and Tuza [ 7 ], we show that the 1- PrExt problem can be solved in polynomial time for chordal graphs.