\(H\)-coloring dichotomy revisited
From MaRDI portal
Publication:817769
DOI10.1016/j.tcs.2005.09.028zbMath1086.68052MaRDI QIDQ817769
Publication date: 20 March 2006
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2005.09.028
68Q25: Analysis of algorithms and problem complexity
05C15: Coloring of graphs and hypergraphs
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Unnamed Item, Unnamed Item, A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP, Smooth digraphs modulo primitive positive constructability and cyclic loop conditions, Loop conditions for strongly connected digraphs, Algebra and the Complexity of Digraph CSPs: a Survey, Pseudo‐loop conditions, Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems), Recent Results on the Algebraic Approach to the CSP, Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs, Unnamed Item, Dualities and algebras with a near-unanimity term, Testing list \(H\)-homomorphisms, \(H\)-colorings of dense hypergraphs, Colouring, constraint satisfaction, and complexity, A strong Mal'cev condition for locally finite varieties omitting the unary type, In praise of homomorphisms, A new line of attack on the dichotomy conjecture, A combinatorial constraint satisfaction problem dichotomy classification conjecture, The local loop lemma, Two-element structures modulo primitive positive constructability, A quasi-Mal'cev condition with unexpected application., Dichotomy for finite tournaments of mixed-type, Unnamed Item
Cites Work
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- On the complexity of H-coloring
- Constraints, consistency and closure
- On the algebraic structure of combinatorial problems
- On sparse graphs with given colorings and homomorphisms.
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- On the Structure of Polynomial Time Reducibility
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item