2 citations · 2 across the 1 of their papers we have counts for
3 papers
cs.CC2026★ 2 cited
The complete classification for quantified equality constraints
Dmitriy Zhuk, Barnaby Martin, Michal Wrona
We prove that QCSP is PSpace-complete, settling a question open for more than ten years. This completes the complexity classification for the QCSP…
cs.DM2026
Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs
Jan Bok, Nikola Jedlickova, Barnaby Martin +3
A (proper) colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. Hence, every injec…
cs.CC2025
Graph Homomorphism, Monotone Classes and Bounded Pathwidth
Tala Eagling-Vose, Barnaby Martin, Daniel Paulusma +1
In recent work by Johnson et al. (2022), a framework was described for the study of graph problems over classes specified by omitting each of a finite set of graphs as subgraphs. I…