Forbidden lifts (NP and CSP for combinatorialists)
From MaRDI portal
Publication:2427542
DOI10.1016/j.ejc.2007.11.027zbMath1213.68323arXiv0706.1704OpenAlexW1974576324MaRDI QIDQ2427542
Publication date: 13 May 2008
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0706.1704
Coloring of graphs and hypergraphs (05C15) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)
Related Items (9)
In praise of homomorphisms ⋮ Binary constraint satisfaction problems defined by excluded topological minors ⋮ A new line of attack on the dichotomy conjecture ⋮ Many Facets of Dualities ⋮ Colouring, constraint satisfaction, and complexity ⋮ Galois connections for patterns: an algebra of labelled graphs ⋮ Dualities in full homomorphisms ⋮ All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms) ⋮ A surprising permanence of old motivations (a not-so-rigid story)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The strong perfect graph theorem
- Monotone clones and congruence modularity
- Star-cutsets and perfect graphs
- Chromatically optimal rigid graphs
- On classes of relations and graphs determined by subobjects and factorobjects
- Algebraic properties and dismantlability of finite posets
- On sparse graphs with given colorings and homomorphisms.
- Jónsson terms and near-unanimity functions in finite posets
- Duality theorems for finite structures (characterising gaps and good characterisations)
- Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
- Constraints, MMSNP and expander relational structures
- Complexity of graph partition problems
- Linear time low tree-width partitions and algorithmic consequences
- A Probabilistic Approach to the Dichotomy Problem
- Monotone clones, residual smallness and congruence distributivity
- Languages that Capture Complexity Classes
- On the Structure of Polynomial Time Reducibility
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Duality and Polynomial Testing of Tree Homomorphisms
- Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
- Order varieties and monotone retractions of finite posets
This page was built for publication: Forbidden lifts (NP and CSP for combinatorialists)
