Showing cs.DMShow all
3 papers · 1 filter
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.DM2025
Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges
Jan Bok, JiÅà Fiala, Petr HlinÄný +2
We initiate the study of computational complexity of graph coverings, aka locally bijective graph homomorphisms, for {\em graphs with semi-edges}. The notion of graph covering is a…
cs.DM2024
List homomorphisms to separable signed graphs
Jan Bok, Richard Brewster, Tomás Feder +2
The complexity of the list homomorphism problem for signed graphs appears difficult to classify. Existing results focus on special classes of signed graphs, such as trees and refle…