scientific article; zbMATH DE number 878894

MaRDI QIDQ4878664zbMATH OpenFDO

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

Publication date 24 June 1996

zbMATH Keywords

complexitycoregraph homomorphismsdigraphNP-completehomomorphism dualityoriented tree

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Graph theory (05C99)

Recommendations

• Complexity of tree homomorphisms
• Duality and Polynomial Testing of Tree Homomorphisms
• The core of a graph

Cited in

(18)

• Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality
• Testing subgraphs in directed graphs
• Doppelgangers and Lemke graphs
• scientific article; zbMATH DE number 5531977 (Why is no real title available?)
• Duality in Infinite Graphs
• Graph partitions with prescribed patterns
• scientific article; zbMATH DE number 6083192 (Why is no real title available?)
• The complexity of the matroid homomorphism problem
• Semidefinite programming and its applications to NP problems
• Dual properties within graph theory
• Colorings and girth of oriented planar graphs
• Colouring, constraint satisfaction, and complexity
• Dual equivalence graphs and CAT(0) combinatorics
• Complexity of tree homomorphisms
• On universal graphs for planar oriented graphs of a given girth
• Homomorphisms to oriented paths
• Complexity of homomorphisms to direct products of graphs
• Dualities for Constraint Satisfaction Problems

This page was built for publication:

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