CSP dichotomy for special triads

DOI10.1090/S0002-9939-09-09883-9MaRDI QIDQ3395563zbMATH OpenFDO

Authors Libor Barto, Marcin Kozik, M. Maróti, Todd Niven

Publication date 11 September 2009

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

graph coloringconstraint satisfaction problemtriad

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• CSP dichotomy for special polyads
• On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
• Duality and Polynomial Testing of Tree Homomorphisms
• On the reduction of the CSP dichotomy conjecture to digraphs
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)

Cites work

• scientific article; zbMATH DE number 1670830 (Why is no real title available?)
• scientific article; zbMATH DE number 1487982 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 5485593 (Why is no real title available?)
• Classification of homomorphisms to oriented cycles and of \(k\)-partite satisfiability
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Complexity of tree homomorphisms
• Duality and Polynomial Testing of Tree Homomorphisms
• 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
• The complexity of constraint satisfaction: an algebraic approach
• The effect of two cycles on the complexity of colourings by directed graphs
• Universal Algebra and Hardness Results for Constraint Satisfaction Problems

Cited in

(10)

• On Maltsev digraphs
• On Maltsev digraphs
• CSP dichotomy for special polyads
• Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems
• Residual properties of pre-bipartite digraphs
• On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
• Graph partitions with prescribed patterns
• The complexity of conservative valued CSPs
• Smooth digraphs modulo primitive positive constructability and cyclic loop conditions
• The smallest hard trees

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

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