On the complexity of H-coloring. (English) Zbl 0639.05023

In standard graph colouring adjacent vertices are required to have different colours. If the set of colours itself forms a graph H, then in an H-colouring of G adjacent vertices are required to have adjacent colours. (Thus an H-colouring of G is just a homomorphism of G to H.) The complexity of deciding the H-colourability of an input graph depends on H. For instances, when H is a complete graph with at least three vertices then H-colourability is NP-complete because it is the traditional colourability problem. When H is bipartite, then H-colourability is equivalent to bipartiteness, and so can be decided in polynomial time.
The authors prove that H-colourability is NP-complete in all other cases. That this was the case was a conjecture of Maurer, Sudborough, and Welzl, popularized in one of David Johnson’s NP-completeness columns. It is often not difficult to prove the NP-completeness of H-colouring for particular classes of graphs H, and several such results exist in the literature. The proof of the full conjecture given here is interesting because of the intricate interplay of the various basic reductions and the complex graphs that are employed in them.
Reviewer: P.Hell


05C15 Coloring of graphs and hypergraphs
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Albertson, M.; Catlin, P.; Gibbons, L., Homomorphisms of 3-chromatic graphs, II, (Congr. Numer., 47 (1985)), 19-28 · Zbl 0622.05024
[2] Bloom, G.; Burr, S., On unavoidable digraphs in orientations of graphs, J. Graph Theory, 11, 453-462 (1987) · Zbl 0647.05025
[3] Fellner, W. D., On minimal graphs, Theoret. Comput. Sci., 17, 103-110 (1982) · Zbl 0473.68063
[4] Garey, M. R.; Johnson, D. S., The complexity of near-optimal graph coloring, J. Assoc. Comput. Mach., 23, 43-49 (1976) · Zbl 0322.05111
[5] Garey, M. R.; Johnson, D. S.; So, H. C., An application of graph coloring to printed circuit testing, IEEE Trans. Circuits and Systems, Cas 23, 591-598 (1976) · Zbl 0342.94021
[6] Garey, M. R.; Johnson, D. S., (Computers and Intractability (1979), Freeman: Freeman San Francisco) · Zbl 0411.68039
[7] Häggkvist, R.; Hell, P.; Miller, D. J.; Neumann-Lara, V., On multiplicative graphs, and the product conjecture, Combinatorica, 8, 63-74 (1988) · Zbl 0657.05028
[8] Hedrlín, Z.; Pultr, A., Symmetric relations (undirected graphs) with given semigroups, Monatsh. Math., 69, 318-322 (1965) · Zbl 0139.24803
[9] Hell, P., Absolute planar retracts and the four-color conjecture, J. Combin. Theory B, 17, 5-10 (1974) · Zbl 0267.05102
[10] Hell, P.; Nešetřil, J., Cohomomorphisms of graphs and hypergraphs, Math. Nachr., 87, 53-61 (1979) · Zbl 0435.05050
[11] Irving, R. W., NP-completeness of a family of graph-colouring problems, Discrete Appl. Math., 5, 111-117 (1983) · Zbl 0504.05032
[12] Johnson, D. S., Worst case behaviour of graph coloring algorithms, (Proceedings 5th Southeastern Conference on Combinatorics, Graph Theory, and Computing. Proceedings 5th Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Math. (1974)), 513-527 · Zbl 0308.05109
[13] Johnson, D. S., The NP-completeness column: An ongoing guide, J. Algorithms, 3, 89-99 (1982) · Zbl 0494.68048
[14] Komárek, P., Some new good characterizations of directed graphs, Casopis Pěst. Mat., 51, 348-354 (1984) · Zbl 0569.05022
[15] Levin, L. A., Universal sequential search problems, Problems Inform. Transmission, 9, 265-266 (1973)
[16] Leighton, F. T., A graph coloring algorithm for large scheduling problems, J. Res. Nat. Bur. Standards, 84, 489-496 (1979) · Zbl 0437.68021
[17] Maurer, H. A.; Salomaa, A.; Wood, D., Colorings and interpretations: A connection between graphs and grammar forms, Discrete Appl. Math., 3, 119-135 (1981) · Zbl 0466.05034
[18] Maurer, H. A.; Sudborough, J. H.; Welzl, E., On the complexity of the general coloring problem, Inform. and Control, 51, 123-145 (1981) · Zbl 0502.68015
[19] Nešetřil, J., Representations of graphs by means of products and their complexity, MFCS, 94-102 (1982) · Zbl 0462.68044
[20] Nešetřil, J.; Pultr, A., On classes of relations and graphs determined by subobjects and factorobjects, Discrete Math., 22, 287-300 (1978) · Zbl 0388.05039
[21] W gderson, A., Improving the performance guarantee for approximate graph coloring, J. Assoc. Comput. Math., 30, 729-735 (1983) · Zbl 0627.68057
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.