Surjective H-Colouring over Reflexive Digraphs

DOI10.1145/3282431zbMath1485.68190arXiv1709.09486OpenAlexW2963569011WikidataQ130952119 ScholiaQ130952119MaRDI QIDQ5205804

Daniël Paulusma, Benoit Larose, Barnaby Martin

Publication date: 16 December 2019

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1709.09486

zbMATH Keywords

computational complexityconstraint satisfactionuniversal algebraalgorithmic graph theorysurjective H-coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (1)

A reflexive digraph that is retraction trivial but not endomorphism trivial

This page was built for publication: Surjective H-Colouring over Reflexive Digraphs