Precoloring Extension III: Classes of Perfect Graphs
Mihály Hujter, Zs. Tuza · Combinatorics Probability Computing · 1996
We continue the study of the following general problem on the vertex colourings of graphs. Suppose that some vertices of a graphGare assigned to some colours. Can this ‘precolouring’ be extended to a proper colouring ofGwith at mostkcolours (for some givenk)? Here we investigate the complexity status of precolouring extendibility on some classes of perfect graphs, giving good characterizations (necessary and sufficient conditions) that lead to algorithms with linear or polynomial running time. It is also shown how a larger subclass of perfect graphs can be derived from graphs containing no induced path on four vertices.