Duality and Polynomial Testing of Tree Homomorphisms

DOI10.1090/S0002-9947-96-01537-1zbMath0877.05055OpenAlexW1825515612MaRDI QIDQ4889961

Jaroslav 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

digraphcharacterizationhomomorphismcolouring problemtree dualitybounded treewidth dualitypolynomial testingtrids

Mathematics Subject Classification ID

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

Related Items (37)

Quantified Constraint Satisfaction Problem on Semicomplete Digraphs ⋮ Colorings and girth of oriented planar graphs ⋮ Classification of a Class of Counting Problems Using Holographic Reductions ⋮ No finite-infinite antichain duality in the homomorphism poset of directed graphs ⋮ Dualities and dual pairs in Heyting algebras ⋮ Algorithms for partition of some class of graphs under compaction and vertex-compaction ⋮ Towards a dichotomy theorem for the counting constraint satisfaction problem ⋮ Complexity of tree homomorphisms ⋮ List homomorphisms to reflexive graphs ⋮ Residual properties of pre-bipartite digraphs ⋮ On the complexity of \(\mathbb{H}\)-coloring for special oriented trees ⋮ The smallest hard trees ⋮ Semidefinite programming and its applications to NP problems ⋮ A new line of attack on the dichotomy conjecture ⋮ On digraph coloring problems and treewidth duality ⋮ Generalised dualities and maximal finite antichains in the homomorphism order of relational structures ⋮ Forbidden lifts (NP and CSP for combinatorialists) ⋮ Homomorphisms and oriented colorings of equivalence classes of oriented graphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ Universal partial order represented by means of oriented trees and other simple graphs ⋮ The \(C_{k}\)-extended graft construction ⋮ Graph partitions with prescribed patterns ⋮ Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties. ⋮ The complexity of list edge-partitions for simple graphs ⋮ Dichotomy for finite tournaments of mixed-type ⋮ Smooth digraphs modulo primitive positive constructability and cyclic loop conditions ⋮ \(H\)-coloring degree-bounded (acyclic) digraphs ⋮ Finite paths are universal ⋮ Finite paths are universal ⋮ CSP dichotomy for special triads ⋮ A surprising permanence of old motivations (a not-so-rigid story) ⋮ A note on maxflow-mincut and homomorphic equivalence in matroids ⋮ On universal graphs for planar oriented graphs of a given girth ⋮ Dualities for Constraint Satisfaction Problems ⋮ Duality theorems for finite structures (characterising gaps and good characterisations) ⋮ Density via duality. ⋮ The complexity of partition functions

This page was built for publication: Duality and Polynomial Testing of Tree Homomorphisms