Interval edge coloring of a graph with forbidden colors

AbstractThis paper is complementary to Kubale (1989). We consider herein a problem of interval coloring the edges of a graph under the restriction that certain colors cannot be used for some edges. We give lower and upper bounds on the minimum number of colors required for such a coloring. Since the general problem is strongly NP-complete, we investigate its complexity in some special cases with particular reference to those that can be solved by polynomial-time algorithms