Interval vertex-coloring of a graph with forbidden colors. (English) Zbl 0682.05033

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.
Reviewer: M.Kubale


05C15 Coloring of graphs and hypergraphs
Full Text: DOI


[1] Erdös, P.; Rubin, A. L.; Taylor, H., Choosability in graphs, (Proc. West Coast Conf. on Combinatorics, Graphs Theory and Computing (1979), Humboldt State University), 125-157 · Zbl 0469.05032
[2] Even, S.; Itai, A.; Shamir, A., On the complexity of timetable and multicommodity flow problems, SIAM J. Comput., 5, 691-703 (1976) · Zbl 0358.90021
[3] Frederickson, G. N., Scheduling unit-time tasks with integer release times and deadlines, Inf. Process. Lett., 16, 171-173 (1983) · Zbl 0508.68023
[4] Johnson, D. S., The NP-completeness column: An ongoing guide, J. Algorithms, 4, 189-203 (1983) · Zbl 0509.68035
[5] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thather, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-103 · Zbl 0366.68041
[6] Kubale, M., The complexity of scheduling independent two-processor tasks on dedicated processors, Inf. Process. Lett., 24, 141-147 (1987) · Zbl 0653.68015
[7] M. Kubale, Graph coloring, in: A. Kent, J.G. Williams, eds., Encyclopedia of Microcomputers (Dekker, New York) (to appear).; M. Kubale, Graph coloring, in: A. Kent, J.G. Williams, eds., Encyclopedia of Microcomputers (Dekker, New York) (to appear). · Zbl 0531.05035
[8] Simons, B.; Sipser, M., On scheduling unit-length jobs with multiple release time/deadline intervals, Oper. Res., 32, 80-88 (1984) · Zbl 0531.90048
[9] Tomita, E.; Tanaka, A.; Takahashi, H., The worst-case time complexity for finding all the cliques, (Technical Report VEC-TR-C5 (1988), University of Electro-Communications: University of Electro-Communications Tokyo) · Zbl 1091.68562
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.