Complexity of tree homomorphisms

DOI10.1016/0166-218X(96)00099-6MaRDI QIDQ1923593zbMATH OpenOpenAlexFDO

Authors J. Nešetřil, Pavol Hell, Xuding Zhu

Publication date 18 August 1997

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

digraphhomomorphism problemstree

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Graph theory (including graph drawing) in computer science (68R10)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 878894
• Duality and Polynomial Testing of Tree Homomorphisms
• The complexity of restricted graph homomorphisms
• On the complexity of \(\mathbb{H}\)-coloring for special oriented trees

Cites work

• A Polynomial Algorithm for Homomorphisms to Oriented Cycles
• Duality and Polynomial Testing of Tree Homomorphisms
• Hereditarily hard \(H\)-colouring problems
• Homomorphisms of graphs and of their orientations
• Homomorphisms to oriented cycles
• Homomorphisms to oriented paths
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 878894 (Why is no real title available?)
• Images of rigid digraphs
• List homomorphisms to reflexive graphs
• Monotone monadic SNP and constraint satisfaction
• On multiplicative graphs and the product conjecture
• On the complexity of colouring by superdigraphs of bipartite graphs
• On the complexity of H-coloring
• On the complexity of the general coloring problem
• Polynomial graph-colorings
• Symmetric graphs and interpretations
• The Complexity of Colouring by Semicomplete Digraphs
• The core of a graph
• The effect of two cycles on the complexity of colourings by directed graphs
• The Existence of Homomorphisms to Oriented Cycles

Cited in

(27)

• Homomorphisms to oriented paths
• Complexity of homomorphisms to direct products of graphs
• On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
• The complexity of tropical graph homomorphisms
• On digraph coloring problems and treewidth duality
• Graph partitions with prescribed patterns
• Dichotomy for finite tournaments of mixed-type
• Adjusted interval digraphs
• The complexity of approximately counting tree homomorphisms
• CSP dichotomy for special triads
• scientific article; zbMATH DE number 1335884 (Why is no real title available?)
• Colouring, constraint satisfaction, and complexity
• Mineurs d'arbres avec racines
• scientific article; zbMATH DE number 878894 (Why is no real title available?)
• Duality and Polynomial Testing of Tree Homomorphisms
• Smooth digraphs modulo primitive positive constructability and cyclic loop conditions
• Algebra and the complexity of digraph CSPs: a survey
• On a directed tree problem motivated by a newly introduced graph product
• Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
• The Space Complexity of k-Tree Isomorphism
• Classes of Tree Homomorphisms with Decidable Preservation of Regularity
• Minimum Cost Homomorphisms to Reflexive Digraphs
• The smallest hard trees
• Residual properties of pre-bipartite digraphs
• The complexity of the matroid homomorphism problem
• Complexity analysis of tree share structure
• A more general theory of static approximations for conjunctive queries

This page was built for publication: Complexity of tree homomorphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1923593)