Surjective \texttt{H}-colouring over reflexive digraphs
algorithmic graph theorycomputational complexityconstraint satisfactionsurjective H-coloringuniversal algebra
Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
- A Characterisation of First-Order Constraint Satisfaction Problems
- A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
- Algebra and the complexity of digraph CSPs: a survey
- Algorithms for partition of some class of graphs under compaction and vertex-compaction
- An algebraic hardness criterion for surjective constraint satisfaction.
- Bi‐arc graphs and the complexity of list homomorphisms
- Classifying the Complexity of Constraints Using Finite Algebras
- Coloring mixed hypertrees
- Complexity of conservative constraint satisfaction problems
- Computational complexity of compaction to irreflexive cycles
- Computational Complexity of Compaction to Reflexive Cycles
- Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
- Computing vertex-surjective homomorphisms to partially reflexive trees
- Digraph matrix partitions and trigraph homomorphisms
- Finite posets and topological spaces in locally finite varieties
- scientific article; zbMATH DE number 3150485 (Why is no real title available?)
- List homomorphisms and circular arc graphs
- List homomorphisms to reflexive graphs
- Majority constraints have bounded pathwidth duality
- Reflexive digraphs with near unanimity polymorphisms
- Retractions to Pseudoforests
- Surjective \(H\)-colouring: new hardness results
- Term minimal algebras
- The Complexity of Colouring by Semicomplete Digraphs
- The complexity of surjective homomorphism problems-a survey
- The computational complexity of disconnected cut and \(2 K_2\)-partition
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The structure of finite algebras
This page was built for publication: Surjective \texttt{H}-colouring over reflexive digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3304148)
