Duality and Polynomial Testing of Tree Homomorphisms
From MaRDI portal
Publication:4889961
DOI10.1090/S0002-9947-96-01537-1zbMath0877.05055MaRDI 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
digraph; characterization; homomorphism; colouring problem; tree duality; bounded treewidth duality; polynomial testing; trids
68Q25: Analysis of algorithms and problem complexity
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
05C20: Directed graphs (digraphs), tournaments
Related Items
Smooth digraphs modulo primitive positive constructability and cyclic loop conditions, Quantified Constraint Satisfaction Problem on Semicomplete Digraphs, Classification of a Class of Counting Problems Using Holographic Reductions, Dualities for Constraint Satisfaction Problems, Finite paths are universal, Finite paths are universal, The smallest hard trees, Semidefinite programming and its applications to NP problems, Algorithms for partition of some class of graphs under compaction and vertex-compaction, Colouring, constraint satisfaction, and complexity, No finite-infinite antichain duality in the homomorphism poset of directed graphs, Dualities and dual pairs in Heyting algebras, Residual properties of pre-bipartite digraphs, The complexity of list edge-partitions for simple graphs, \(H\)-coloring degree-bounded (acyclic) digraphs, Towards a dichotomy theorem for the counting constraint satisfaction problem, A new line of attack on the dichotomy conjecture, A surprising permanence of old motivations (a not-so-rigid story), List homomorphisms to reflexive graphs, Colorings and girth of oriented planar graphs, Homomorphisms and oriented colorings of equivalence classes of oriented graphs, On universal graphs for planar oriented graphs of a given girth, On the complexity of \(\mathbb{H}\)-coloring for special oriented trees, Universal partial order represented by means of oriented trees and other simple graphs, A note on maxflow-mincut and homomorphic equivalence in matroids, Duality theorems for finite structures (characterising gaps and good characterisations), Density via duality., Complexity of tree homomorphisms, The \(C_{k}\)-extended graft construction, 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), Graph partitions with prescribed patterns, Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties., Dichotomy for finite tournaments of mixed-type, The complexity of partition functions, CSP dichotomy for special triads
