CSP DICHOTOMY FOR SPECIAL POLYADS

DOI10.1142/S0218196713500215zbMath1277.68220MaRDI QIDQ2852579

Jakub Bulín, Libor Barto

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) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

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

Cites Work

• Bounded width problems and algebras
• Existence theorems for weakly symmetric operations
• On the complexity of H-coloring
• On multiplicative graphs and the product conjecture
• Polynomial graph-colorings
• Classification of Homomorphisms to Oriented Cycles and of k-Partite Satisfiability
• CSP dichotomy for special triads
• 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
• Closure properties of constraints
• Classifying the Complexity of Constraints Using Finite Algebras

This page was built for publication: CSP DICHOTOMY FOR SPECIAL POLYADS