Complexity of tree homomorphisms

DOI10.1016/0166-218X(96)00099-6zbMath0868.05018OpenAlexW2086916741MaRDI QIDQ1923593

Jaroslav 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

treedigraphhomomorphism problems

Mathematics Subject Classification ID

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

Related Items

The Complexity of Approximately Counting Tree Homomorphisms ⋮ Residual properties of pre-bipartite digraphs ⋮ On the complexity of \(\mathbb{H}\)-coloring for special oriented trees ⋮ The smallest hard trees ⋮ On digraph coloring problems and treewidth duality ⋮ Colouring, constraint satisfaction, and complexity ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ The complexity of tropical graph homomorphisms ⋮ Graph partitions with prescribed patterns ⋮ Dichotomy for finite tournaments of mixed-type ⋮ Smooth digraphs modulo primitive positive constructability and cyclic loop conditions ⋮ Minimum Cost Homomorphisms to Reflexive Digraphs ⋮ CSP dichotomy for special triads ⋮ Adjusted Interval Digraphs ⋮ A more general theory of static approximations for conjunctive queries

Cites Work

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