Hell, Pavol; Nešetřil, Jaroslav; Zhu, Xuding Complexity of tree homomorphisms. (English) Zbl 0868.05018 Discrete Appl. Math. 70, No. 1, 23-36 (1996). Let \(T\) be an oriented tree and consider the complexity of deciding whether or not a given digraph is homomorphic to \(T\). A class of simple trees with NP-complete homomorphism problems is identified, the smallest tree having 45 vertices. A list of all subtrees that are necessary in order to get NP-complete homomorphism problems for a tree is presented. Reviewer: P.Kirschenhofer (Leoben) Cited in 15 Documents MSC: 05C05 Trees 68R10 Graph theory (including graph drawing) in computer science 05C15 Coloring of graphs and hypergraphs 05C38 Paths and cycles Keywords:digraph; homomorphism problems; tree PDFBibTeX XMLCite \textit{P. Hell} et al., Discrete Appl. Math. 70, No. 1, 23--36 (1996; Zbl 0868.05018) Full Text: DOI Link References: [1] Bang-Jansen, 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 [2] Bang-Jansen, J.; Hell, P.; MacGilivray, G., The complexity of colourings by semicomplete digraphs, SIAM J. Discrete Math., 1, 281-289 (1988) [3] 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 [4] Bang-Jensen, J.; Hell, P.; MacGillivray, G., Hereditarily hard colouring problems, Discrete Math., 138, 75-92 (1995) · Zbl 0816.68090 [5] Feder, T., Classification of homomorphisms to oriented cycles (draft) (1994), manuscript [6] Feder, T.; Hell, P., List homomorphisms to reflexive graphs (1995), manuscript · Zbl 0904.05078 [7] Feder, T.; Hell, P.; Huang, J., List homomorphisms to bipartite graphs (1995), manuscript [8] Feder, T.; Vardi, M. Y., Monotone monadic SNP and constraint satisfaction, (25th Annu. ACM Symp. on Theory of Computing (1993)), 612-622 · Zbl 1310.68086 [9] Gary, M. R.; Johnson, D. S., Computers and Intractability (1979), Freeman: Freeman NY [10] Gutjahr, W., Graph colourings, (Ph.D. Thesis (1991), Free University Berlin) [11] Gutjahr, W.; Welzl, E.; Woeginger, G., Polynomial graph colourings, Discrete Appl. Math., 35, 29-46 (1992) [12] Häggkvist, R.; Hell, P.; Miller, D. J.; Neumann Lara, V., On multiplicative graphs and the product conjecture, Combinatorica, 8, 71-81 (1988) · Zbl 0657.05028 [13] Hell, P.; Nešetřil, J., Homomorphisms of graphs and their orientations, Monatsh. Math., 85, 39-48 (1978) · Zbl 0375.05023 [14] Hell, P.; Nešetřil, J., On the complexity of H-colouring, J. Combin. Theory Ser., 48, 92-110 (1990) · Zbl 0639.05023 [15] Hell, P.; Nešetřil, J., Images of rigid digraphs, European J. Combin., 12, 33-42 (1991) · Zbl 0715.05027 [16] Hell, P.; Nešetřil, J., The core of a graph, Discrete Math., 109, 117-126 (1992) · Zbl 0803.68080 [17] Hell, P.; Nešetřil, J.; Zhu, X., Duality and polynomial testing of tree homomorphisms, (Technical Report, KAM series 93-243 (1993), Department of Applied Mathematics, Charles University: Department of Applied Mathematics, Charles University Prague) · Zbl 0877.05055 [18] Hell, P.; Nešetřil, J.; Zhu, X., Duality of graph homomorphisms, (Combinatorics, Paul Erdös is Eighty, Vol. 2 (1993), Bolyai Society Mathematical Studies: Bolyai Society Mathematical Studies Budapest, Hungary) · Zbl 0846.05093 [19] P. Hell, J. Nešetřil and X. Zhu, Duality and polynomial testing of tree homomorphisms, Trans. AMS, in print.; P. Hell, J. Nešetřil and X. Zhu, Duality and polynomial testing of tree homomorphisms, Trans. AMS, in print. [20] Hell, P.; Zhou, H.; Zhu, X., Homomorphisms to oriented cycles, Combinatorica, 13, 421-433 (1993) · Zbl 0794.05037 [21] Hell, P.; Zhu, X., Homomorphisms to oriented paths, Discrete. Math., 132, 107-114 (1994) · Zbl 0819.05030 [22] Hell, P.; Zhu, X., The existence of homomorphisms to oriented cycles, SIAM J. Discrete Math., 8, 208-222 (1995) · Zbl 0831.05059 [23] G. MacGillivray, On the complexity of colourings by vertex-transitive and arc-transitive digraphs, SIAM J. Discrete Math. in press.; G. MacGillivray, On the complexity of colourings by vertex-transitive and arc-transitive digraphs, SIAM J. Discrete Math. in press. [24] 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 [25] Welzl, E., Symmetric graphs and interpretations, J. Combin. Theory Ser. B, 37, 235-244 (1984) · Zbl 0547.05058 [26] X. Zhu, A polynomial algorithm for homomorphisms to oriented cycles, J. Algorithms, to appear.; X. Zhu, A polynomial algorithm for homomorphisms to oriented cycles, J. Algorithms, to appear. · Zbl 0836.68089 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.