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

complexitycoredigraphgraph homomorphismshomomorphism dualityNP-completeoriented 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

(19)

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

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)