Complexity of tree homomorphisms
type: Item
instance of: scholarly article
title: Complexity of tree homomorphisms
zbMATH Open document ID: 0868.05018
DOI: 10.1016/0166-218X(96)00099-6
author: J. Nešetřil
author: Pavol Hell
author: Xuding Zhu
published in: Discrete Applied Mathematics
publication date: 1997-08-18T00:00:00Z
full work available at URL: dam
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.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 933107
zbMATH Keywords: digraph
zbMATH Keywords: homomorphism problems
zbMATH Keywords: tree
reviewed by: Peter Kirschenhofer
MaRDI profile type: Publication
cites work: The effect of two cycles on the complexity of colourings by directed graphs
cites work: The Complexity of Colouring by Semicomplete Digraphs
cites work: On the complexity of colouring by superdigraphs of bipartite graphs
cites work: Hereditarily hard \(H\)-colouring problems
cites work: List homomorphisms to reflexive graphs
cites work: Monotone monadic SNP and constraint satisfaction
cites work: Q4198056
cites work: Polynomial graph-colorings
cites work: On multiplicative graphs and the product conjecture
cites work: Homomorphisms of graphs and of their orientations
cites work: On the complexity of H-coloring
cites work: Images of rigid digraphs
cites work: The core of a graph
cites work: Duality and Polynomial Testing of Tree Homomorphisms
cites work: Q4878664
cites work: Homomorphisms to oriented cycles
cites work: Homomorphisms to oriented paths
cites work: The Existence of Homomorphisms to Oriented Cycles
cites work: On the complexity of the general coloring problem
cites work: Symmetric graphs and interpretations
cites work: A Polynomial Algorithm for Homomorphisms to Oriented Cycles
OpenAlex ID: W2086916741
description: scientific article; zbMATH DE number 933107