Interval vertex-coloring of a graph with forbidden colors (Q1823960)

The classical model of coloring the vertices of a graph with single colors so that no two adjacent vertices are colored the same is too limited to be useful in many practical applications. Therefore one must consider more general notions of graph coloring and this article is devoted to one of such generalizations. The author considers a problem of interval coloring the vertices of a graph under the stipulation that certain colors cannot be used for some vertices. Lower and upper bounds on the minimum number of colors required for such a coloring are given. Since the general problem is NP-complete, he investigates its complexity in some special cases with a particular reference to those that can be solved by a polynomial-time algorithm.