scientific article; zbMATH DE number 878894

zbMATH Open0846.05093MaRDI QIDQ4878664FDOQ4878664

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

Publication date: 24 June 1996

Title of this publication is not available (Why is that?)

Recommendations

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

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)

Cited In (18)

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

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)