\(H\)-coloring dichotomy revisited

DOI10.1016/j.tcs.2005.09.028zbMath1086.68052OpenAlexW1984264511MaRDI QIDQ817769

Andrei A. Bulatov

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

zbMATH Keywords

complexitygraph colouringconstraint satisfactionalgebraic approach

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (24)

In praise of homomorphisms ⋮ Unnamed Item ⋮ Dualities and algebras with a near-unanimity term ⋮ Testing list \(H\)-homomorphisms ⋮ A strong Mal'cev condition for locally finite varieties omitting the unary type ⋮ Unnamed Item ⋮ A new line of attack on the dichotomy conjecture ⋮ Unnamed Item ⋮ \(H\)-colorings of dense hypergraphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Unnamed Item ⋮ Pseudo‐loop conditions ⋮ A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP ⋮ Dichotomy for finite tournaments of mixed-type ⋮ Smooth digraphs modulo primitive positive constructability and cyclic loop conditions ⋮ Loop conditions for strongly connected digraphs ⋮ The local loop lemma ⋮ Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems) ⋮ Two-element structures modulo primitive positive constructability ⋮ A combinatorial constraint satisfaction problem dichotomy classification conjecture ⋮ Recent Results on the Algebraic Approach to the CSP ⋮ Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs ⋮ A quasi-Mal'cev condition with unexpected application.

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

This page was built for publication: \(H\)-coloring dichotomy revisited