CSP dichotomy for special triads

DOI10.1090/S0002-9939-09-09883-9zbMATH Open1215.05179MaRDI QIDQ3395563FDOQ3395563

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)

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)

zbMATH Keywords

graph coloringconstraint satisfaction problemtriad

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Existence theorems for weakly symmetric operations
• On the complexity of H-coloring
• 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
• On multiplicative graphs and the product conjecture
• Title not available (Why is that?)
• The complexity of constraint satisfaction: an algebraic approach
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Universal Algebra and Hardness Results for Constraint Satisfaction Problems
• Polynomial graph-colorings
• Duality and Polynomial Testing of Tree Homomorphisms
• Complexity of tree homomorphisms
• Classification of homomorphisms to oriented cycles and of \(k\)-partite satisfiability
• The effect of two cycles on the complexity of colourings by directed graphs

Cited In (10)

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

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)