In praise of homomorphisms
From MaRDI portal
Publication:826325
DOI10.1016/j.cosrev.2020.100352zbMath1506.08001OpenAlexW3129539141MaRDI QIDQ826325
Publication date: 20 December 2021
Published in: Computer Science Review (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cosrev.2020.100352
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matroid invariants and counting graph homomorphisms
- Strongly polynomial sequences as interpretations
- Colouring, constraint satisfaction, and complexity
- Dualities and dual pairs in Heyting algebras
- A strong Mal'cev condition for locally finite varieties omitting the unary type
- The fractional version of Hedetniemi's conjecture is true
- Regular families of forests, antichains and duality pairs of relational structures
- Generalized chromatic polynomials
- Graph invariants related to statistical mechanical models: Examples and problems
- \(H\)-coloring dichotomy revisited
- Polynomial graph invariants from homomorphism numbers
- Efficient algorithms for counting parameterized list \(H\)-colorings
- From a zoo to a zoology: Towards a general theory of graph polynomials
- A combinatorial constraint satisfaction problem dichotomy classification conjecture
- Theory of relations. Transl. from the French by P. Clote
- On the complexity of H-coloring
- On the arc-chromatic number of a digraph
- On classes of relations and graphs determined by subobjects and factorobjects
- On colorings of graphs without short cycles
- On the algebraic structure of combinatorial problems
- A survey on Hedetniemi's conjecture
- On sparse graphs with given colorings and homomorphisms.
- Graph products, Fourier analysis and spectral techniques
- The restrictive \(H\)-coloring problem
- Networks of constraints: Fundamental properties and applications to picture processing
- Duality theorems for finite structures (characterising gaps and good characterisations)
- A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
- Chromatic invariants for finite graphs: Theme and polynomial variations
- Hedetniemi's conjecture is asymptotically false
- Counterexamples to Hedetniemi's conjecture
- A note on Hedetniemi's conjecture, Stahl's conjecture and the Poljak-Rödl function
- All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)
- On inverse powers of graphs and topological implications of Hedetniemi's conjecture
- Complexity issues on bounded restrictive \(H\)-coloring
- Forbidden lifts (NP and CSP for combinatorialists)
- Constraints, MMSNP and expander relational structures
- Structural sparsity
- Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
- A New Proof of the H-Coloring Dichotomy
- Projectivity and independent sets in powers of graphs
- Note on projective graphs
- Constraint Satisfaction with Countable Homogeneous Templates
- Homomorphism preservation theorems
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
- A new line of attack on the dichotomy conjecture
- Automorphism groups and Ramsey properties of sparse graphs
- A Most General Edge Elimination Polynomial
- Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality
- Operations with structures
- Hedetniemi's conjecture---a survey
