Duality and Polynomial Testing of Tree Homomorphisms

DOI10.1090/S0002-9947-96-01537-1MaRDI QIDQ4889961zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

characterizationdigraphhomomorphismcolouring problemtree dualitybounded treewidth dualitypolynomial testingtrids

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
• Complexity of tree homomorphisms
• scientific article; zbMATH DE number 878894
• scientific article; zbMATH DE number 932194
• CSP dichotomy for special triads

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
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Dualities for Constraint Satisfaction Problems
• Dichotomy for finite tournaments of mixed-type
• Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
• scientific article; zbMATH DE number 2061631 (Why is no real title available?)
• The complexity of list edge-partitions for simple graphs
• Dualities and dual pairs in Heyting algebras
• Colorings and girth of oriented planar graphs
• The \(C_{k}\)-extended graft construction
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• On universal graphs for planar oriented graphs of a given girth
• Classification of a Class of Counting Problems Using Holographic Reductions
• \(H\)-coloring degree-bounded (acyclic) digraphs
• Finite paths are universal
• The smallest hard trees
• A new line of attack on the dichotomy conjecture
• Dichotomy for tree-structured trigraph list homomorphism problems
• 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)
• Adjoint functors and tree duality
• Semidefinite programming and its applications to NP problems
• 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
• Algorithms for partition of some class of graphs under compaction and vertex-compaction
• A note on maxflow-mincut and homomorphic equivalence in matroids
• No finite-infinite antichain duality in the homomorphism poset of directed graphs
• On digraph coloring problems and treewidth duality
• Forbidden lifts (NP and CSP for combinatorialists)

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)