Duality and Polynomial Testing of Tree Homomorphisms
DOI10.1090/S0002-9947-96-01537-1zbMATH Open0877.05055OpenAlexW1825515612MaRDI QIDQ4889961FDOQ4889961
Authors: J. Nešetřil, Xuding Zhu, Pavol Hell 
Publication date: 8 December 1997
Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1090/s0002-9947-96-01537-1
Recommendations
characterizationdigraphhomomorphismcolouring problemtree dualitybounded treewidth dualitypolynomial testingtrids
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)
Cited In (42)
- Smooth digraphs modulo primitive positive constructability and cyclic loop conditions
- Duality theorems for finite structures (characterising gaps and good characterisations)
- Graph partitions with prescribed patterns
- Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
- CSP dichotomy for special triads
- Polynomial graph-colorings
- Density via duality.
- Colouring, constraint satisfaction, and complexity
- Dualities for Constraint Satisfaction Problems
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- Dichotomy for finite tournaments of mixed-type
- Title not available (Why is that?)
- Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
- The complexity of list edge-partitions for simple graphs
- Dualities and dual pairs in Heyting algebras
- The \(C_{k}\)-extended graft construction
- Colorings and girth of oriented planar graphs
- Homomorphisms and oriented colorings of equivalence classes of oriented graphs
- Classification of a Class of Counting Problems Using Holographic Reductions
- On universal graphs for planar oriented graphs of a given girth
- Finite paths are universal
- \(H\)-coloring degree-bounded (acyclic) digraphs
- The smallest hard trees
- Dichotomy for tree-structured trigraph list homomorphism problems
- A new line of attack on the dichotomy conjecture
- The complexity of partition functions
- Finite paths are universal
- Quantified constraint satisfaction problem on semicomplete digraphs
- The recognition of bound quivers using edge-coloured homomorphisms
- A surprising permanence of old motivations (a not-so-rigid story)
- Semidefinite programming and its applications to NP problems
- Adjoint functors and tree duality
- On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
- Complexity of tree homomorphisms
- Residual properties of pre-bipartite digraphs
- Universal partial order represented by means of oriented trees and other simple graphs
- List homomorphisms to reflexive graphs
- A note on maxflow-mincut and homomorphic equivalence in matroids
- Algorithms for partition of some class of graphs under compaction and vertex-compaction
- On digraph coloring problems and treewidth duality
- Forbidden lifts (NP and CSP for combinatorialists)
- No finite-infinite antichain duality in the homomorphism poset of directed graphs
This page was built for publication: Duality and Polynomial Testing of Tree Homomorphisms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4889961)
