20 citations · 75 across the 44 of their papers we have counts for
3 papers · 1 filter
Surjective H-Colouring over Reflexive Digraphs
Benoit Larose, Barnaby Martin, Daniel Paulusma
The Surjective H-Colouring problem is to test if a given graph allows a vertex-surjective homomorphism to a fixed graph H. The complexity of this problem has been well studied for…
The complexity of quantified constraints using the algebraic formulation
Catarina Carvalho, Barnaby Martin, Dmitriy Zhuk
Let A be an idempotent algebra on a finite domain. We combine results of Chen, Zhuk and Carvalho et al. to argue that if A satisfies the polynomially generated powers property (PGP…
Surjective H-Colouring: New Hardness Results
Petr Golovach, Matthew Johnson. Barnaby Martin, Daniel Paulusma +1
A homomorphism from a graph G to a graph H is a vertex mapping f from the vertex set of G to the vertex set of H such that there is an edge between vertices f(u) and f(v) of H when…