Colouring, constraint satisfaction, and complexity

2008/10/22 by Pavol Hell, Jaroslav Nešetřil · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Artificial intelligence #Class (philosophy) #Complexity and Algorithms in Graphs #Complexity of constraint satisfaction #Computer science #Conjecture #Constraint (computer-aided design) #Constraint graph #Constraint programming #Constraint satisfaction #Constraint satisfaction dual problem #Constraint satisfaction problem #Discrete mathematics #Focus (optics) #Graph #Graph Labeling and Dimension Problems #Homomorphism #Local consistency #Mathematical optimization #Mathematics #Theoretical computer science

paper · doi:10.1016/j.cosrev.2008.10.003

openalex publication_date 2008/10/22 · crossref created 2008/10/22 · crossref issued 2008/12/01 · crossref published 2008/12/01 · crossref published-print 2008/12/01 · openalex created_date 2025/10/10 · crossref deposited 2025/10/28 · crossref indexed 2025/10/28 · openalex updated_date 2026/04/09

Citations

• Minimum Cost Homomorphisms to Locally Semicomplete and Quasi-Transitive Digraphs
• Minimum Cost Homomorphisms to Proper Interval Graphs and Bigraphs
• The strong perfect graph theorem
• Expander graphs and their applications
• A linear-time algorithm for testing the truth of certain quantified boolean formulas
• Absolute retracts of bipartite graphs
• On the Structure of Polynomial Time Reducibility
• The core of a graph
• On the complexity of H-coloring
• The Ramsey number R(3, t) has order of magnitude t2/log t
• Decomposition by clique separators
• Proof verification and the hardness of approximation problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Bisplit graphs

Cited by

• Graph homomorphism [wikipedia]