Precoloring extension. I: Interval graphs (Q1198648)

The precoloring extension problem is defined as follows: given an integer \(k\geq 2\), a graph \(G=(V,E)\) with \(| V|\geq k\), a vertex-subest \(W\subseteq V\), and a proper \(k\)-coloring of the subgraph of \(G\) induced by \(W\), can this \(k\)-coloring be extended to a proper \(k\)-coloring of the whole graph \(G\)? The paper under review is the first in a series of 4 papers on the subject, and it deals with interval graphs. The chromatic number of an interval graph can be bound in linear time. The precoloring extension problem is NP-complete even if each color is used at most twice in the precoloring. This result is proved by a polynomial transformation from the chromatic number problem on circular arc graphs, which was shown to be NP-complete in \textit{M. R. Garey}, \textit{D. S. Johnson}, \textit{G. L. Miller} and \textit{C. H. Papadimitriou} [SIAM J. Algebraic Discrete Methods 1, 216--227 (1980; Zbl 0499.05058)]. It becomes polynomially solvable if each color is used at most once in the precoloring, or if \(k\) is fixed. Before proving these results the authors discuss applications of the precoloring extension problem to scheduling and to VLSI theory.