Some results concerning the complexity of restricted colorings of graphs. (English) Zbl 0755.05036

The complexity of colouring the vertices and edges of a simple graph is considered, where every vertex (or edge) has a set of zero or more forbidden colours and adjacent vertices (or edges) receive different colours. The restricted chromatic number \(\chi(G,F)\) (and the chromatic index \(\chi'(G,F)\), resp.) is the least \(k\) for which there is a restricted \(k\)-colouring of \((G,F)\). The decision problem “Given a graph \(G\), a forbidding function \(F\) and an integer \(k\), is \(\chi(G,F)\leq k?\)” is NP-complete even when restricted to bipartite graphs and \(k=5\). A similar result is obtained for the decision problem for edge coloured graphs. Some classes of graphs (as trees and paths) for which optimal colourings can be obtained in polynomial time are mentioned.


05C15 Coloring of graphs and hypergraphs
Full Text: DOI


[1] Anderson, L. D., Completing partial latin squares, Mat. Fys. Medd. Danske Vid. Selsk., 41, 23-69 (1985)
[2] Cole, R.; Hopcroft, J. E., On edge coloring bipartite graphs, SIAM J. Comput., 11, 540-546 (1982) · Zbl 0486.68062
[3] Erdös, P.; Rubin, A. L.; Taylor, H., Choosability in graphs, Proceedings West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata (1979). Proceedings West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata (1979), Congr. Numer., 26, 125-157 (1979) · Zbl 0469.05032
[4] Even, S.; Itai, A.; Shamir, A., On the complexity of time table and multicommodity flow problems, SIAM J. Comput., 5, 691-703 (1976) · Zbl 0358.90021
[5] Frederickson, G. N., Scheduling unit-time tasks with integer release times and deadlines, Inform. Process. Lett., 16, 171-173 (1983) · Zbl 0508.68023
[6] Gabow, H. N.; Tarjan, R. E., Algorithms for two bottleneck optimization problems, J. Algorithms, 9, 411-417 (1988) · Zbl 0653.90087
[7] Hilton, A. J.W., Embedding incomplete latin rectangles and extending the edge colourings of graphs, Nanta Math., 10, 201-206 (1977) · Zbl 0416.05019
[8] Holyer, I., The NP-completeness of edge-coloring, SIAM J. Comput., 10, 718-720 (1981) · Zbl 0473.68034
[9] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thather, J. W., Complexity of Computer Computations (1972), Plenum: Plenum New York), 85-103 · Zbl 0366.68041
[10] Kubale, M., Interval vertex-coloring of a graph with forbidden colors, Discrete Math., 74, 125-136 (1989) · Zbl 0682.05033
[11] Ryser, H. J., A combinatorial theorem with an application to latin rectangles, Proc. Amer. Math. Soc., 2, 550-552 (1951) · Zbl 0043.01202
[12] Simons, B.; Sipser, M., On scheduling unit-length jobs with multiple release time⧸deadline intervals, Oper. Res., 32, 80-88 (1984) · Zbl 0531.90048
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.