CSP dichotomy for special polyads

DOI10.1142/S0218196713500215zbMATH Open1277.68220MaRDI QIDQ2852579FDOQ2852579

Authors Libor Barto, Jakub Bulín

Publication date 9 October 2013

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

zbMATH Keywords

graph coloringconstraint satisfaction problembounded widthspecial triad

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Recommendations

• CSP dichotomy for special triads
• On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• CSP for binary conservative relational structures
• Asking the Metaquestions in Constraint Tractability

Cites work

• Bounded width problems and algebras
• CSP dichotomy for special triads
• Classification of homomorphisms to oriented cycles and of \(k\)-partite satisfiability
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Existence theorems for weakly symmetric operations
• On multiplicative graphs and the product conjecture
• On the complexity of H-coloring
• Polynomial graph-colorings
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

Cited in

(5)

• CSP dichotomy for special triads
• On Maltsev digraphs
• On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
• Smooth digraphs modulo primitive positive constructability and cyclic loop conditions
• The smallest hard trees

This page was built for publication: CSP dichotomy for special polyads

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2852579)