Bang-Jensen, Jørgen; Hell, Pavol; MacGillivray, Gary Hereditarily hard \(H\)-colouring problems. (English) Zbl 0816.68090 Discrete Math. 138, No. 1-3, 75-92 (1995). Summary: Let \(H\) be a graph (respectively digraph) whose vertices are called ‘colours’. An \(H\)-colouring of a graph (respectively digraph) \(G\) is an assignment of these colours to the vertices of \(G\) so that if \(u\) is adjacent to \(v\) in \(G\), then the colour of \(u\) is adjacent to the colour of \(v\) in \(H\). We continue the study of the complexity of the \(H\)- colouring problem ‘Does a given graph (respectively digraph) admit an \(H\)-colouring?’ For graphs it was proved that the \(H\)-colouring problem is NP-complete whenever \(H\) contains an odd cycle, and is polynomial for bipartite graphs. For direct graphs the situation is quite different, as the addition of an edge to \(H\) can result in the complexity of the \(H\)- colouring problem shifting from NP-complete to polynomial. In fact, there is not even a plausible conjecture as to what makes directed \(H\)- colouring problems difficult in general. Some order may perhaps be found for those digraphs \(H\) in which each vertex has positive in-degree and positive out-degree. In any event, there is at least, in this case, a conjecture of a classification by complexity of these directed \(H\)- colouring problems. Another way, which we propose here, to bring some order to the situation is to restrict our attention to those digraphs \(H\) which, like odd cycles in the case of graphs, are hereditarily hard, i.e., are such that the \(H'\)-colouring problem is NP-hard for any digraph \(H'\) containing \(H\) as a subdigraph. After establishing some properties of the digraphs in this class, we make a conjecture as to precisely which digraphs are hereditarily hard. Surprisingly, this conjecture turns out to be equivalent to the one mentioned earlier. We describe several infinite families of hereditarily hard digraphs, and identify a family of digraphs which are minimal in the sense that it would be sufficient to verify the conjecture for members of that family. Cited in 11 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 68Q25 Analysis of algorithms and problem complexity 05C15 Coloring of graphs and hypergraphs 05C20 Directed graphs (digraphs), tournaments Keywords:H-colouring; digraph PDFBibTeX XMLCite \textit{J. Bang-Jensen} et al., Discrete Math. 138, No. 1--3, 75--92 (1995; Zbl 0816.68090) Full Text: DOI References: [1] Bang-Jensen, J., On the complexity of generalized colourings of directed graphs, (Internal Report No. 3 (1989), Odense Universitet (Institut for Matematik og Datalogi)) [2] Bang-Jensen, J.; Hell, P., The effect of two cycles on the complexity of colourings by directed graphs, Discrete Appl. Math., 26, 1-23 (1990) · Zbl 0697.05029 [3] Bang-Jensen, J.; Hell, P.; MacGillivray, G., The complexity of colourings by semicomplete digraphs, SIAM J. Discrete Math., 1, 281-298 (1988) · Zbl 0678.05018 [4] Bang-Jensen, J.; Hell, P.; MacGillivray, G., On the complexity of colouring by superdigraphs of bipartite graphs, Discrete Math., 109, 27-44 (1992) · Zbl 0783.05047 [5] Brewster, R., Vertex colourings of edge-coloured graphs, (Ph.D. Thesis (1993), Simon Fraser University: Simon Fraser University Burnaby) [6] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Elsevier: Elsevier New York · Zbl 1134.05001 [7] Brouwer, A. E.; Veldman, H. J., Contractability and NP-completeness, J. Graph Theory, 11, 71-79 (1987) · Zbl 0603.05016 [8] Fellner, W. D., On minimal graphs, Theoret. Comput. Sci., 17, 103-110 (1982) · Zbl 0473.68063 [9] Fortune, S.; Hopcroft, J.; Wyllie, J., The directed subgraph homeomorphism problem, Theoret. Comput. Sci., 10, 111-121 (1980) · Zbl 0419.05028 [10] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), W.H. Freedman: W.H. Freedman San Francisco, CA · Zbl 0411.68039 [11] Gutjahr, W., Farbung durch gerichtete Graphen, (Diplomarbeit (1988), Institute for Information Processing, IIG, Technical University Graz) [12] Gutjahr, W., Graph colourings, (Ph.D. Thesis (1991), Free University: Free University Berlin) [13] Gutjahr, W.; Welzl, E.; Woeginger, G., Polynomial graph colourings, Discrete Appl. Math., 35, 29-46 (1992) [14] W. Gutjahr, E. Welzl and G. Woeginger, personal communication 1989.; W. Gutjahr, E. Welzl and G. Woeginger, personal communication 1989. [15] Häggkvist, R.; Hell, P.; Miller, D. J.; Neuman Lara, V., On multiplicative graphs and the product conjecture, Combinatorica, 8, 63-74 (1988) · Zbl 0657.05028 [16] Hell, P.; Nešetřil, J., On the complexity of H-colouring, J.C.T. Ser B, 48, 92-110 (1990) · Zbl 0639.05023 [17] Hell, P.; Nešetřil, J.; Zhu, X., Duality and polynomial testing of tree homomorphisms, manuscript (1993) [18] Hell, P.; Nešetřil, J.; Zhu, X., Complexity of tree homomorphisms, manuscript (1993) [19] P. Hell, H. Zhou and X. Zhu, Homomorphisms to oriented cycles, Combinatorica, to appear.; P. Hell, H. Zhou and X. Zhu, Homomorphisms to oriented cycles, Combinatorica, to appear. [20] P. Hell and X. Zhu, Homomorphisms to oriented paths, Discrete Math., to appear.; P. Hell and X. Zhu, Homomorphisms to oriented paths, Discrete Math., to appear. [21] Hell, P.; Zhu, X., The existence of homomorphisms to oriented cycles, manuscript (1993) [22] Johnson, D. S., The NP-completeness column — An ongoing guide, J. Algorithms, 3, 89-99 (1982) · Zbl 0494.68048 [23] MacGillivray, G., The complexity of generalized colourings, (Ph.D. Thesis (1989), Simon Fraser University: Simon Fraser University Burnaby) [24] MacGillivray, G., The complexity of colouring by vertex-transitive and edge-transitive digraphs, SIAM J. Discrete Math., 4, 297-408 (1991) [25] G. MacGillivray, Graph homomorphisms with infinite targets, Discrete Appl. Math., to appear.; G. MacGillivray, Graph homomorphisms with infinite targets, Discrete Appl. Math., to appear. · Zbl 0812.68101 [26] MacGillivray, G.; Bang-Jensen, J., Further effects of two directed cycles n the complexity of directed H-colouring, J. Combin. Math. Combin. Comput., 10, 35-40 (1991) [27] MacGillivray, G.; Bang-Jensen, J., On the complexity of colouring by digraphs with at most one directed cycle, Ars Combinatoria, 35-A, 175-186 (1993) · Zbl 0840.05022 [28] Maurer, H. A.; Sudborough, J. H.; Welzl, E., On the complexity of the general colouring problem, Inform. and Control, 51, 123-145 (1981) · Zbl 0502.68015 [29] Maurer, H. A.; Salomaa, A.; Wood, D., Colourings and interpretations: a connection between graphs and grammar forms, Discrete Appl. Math., 3, 119-135 (1981) · Zbl 0466.05034 [30] Nešetřil, J., Representations of graphs by means of products and their complexity, (Math. Found. Comput. Sci., Lecture Notes in Computer Science, 118 (1981), Springer: Springer Berlin), 94-102 [31] Nešetřil, J.; Pultr, A., On classes of relations determined by subobjects and factorobjects, Discrete Math., 22, 287-300 (1978) · Zbl 0388.05039 [32] Welzl, E., Colour families are dense, Theoret. Comput. Sci., 17, 29-41 (1982) · Zbl 0482.68063 [33] Zhu, X., A polynomial algorithm for homomorphisms to oriented cycles, manuscript (1991) 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.