\(H\)-coloring dichotomy revisited

DOI10.1016/j.tcs.2005.09.028zbMath1086.68052MaRDI 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

complexity; graph colouring; constraint satisfaction; algebraic approach

Mathematics Subject Classification ID

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

Recent Results on the Algebraic Approach to the CSP, 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, A new line of attack on the dichotomy conjecture, A combinatorial constraint satisfaction problem dichotomy classification conjecture, A quasi-Mal'cev condition with unexpected application., Dichotomy for finite tournaments of mixed-type

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