4 papers · 1 filter
Computational complexity of covering regular trees
Jan Bok, Jiří Fiala, Nikola Jedličková +1
A graph covering projection, also referred to as a locally bijective homomorphism, is a mapping between the vertices and edges of two graphs that preserves incidences and is a loca…
Computational Complexity of Covering Colored Mixed Multigraphs with Simple Degree Partitions
Jan Bok, Jiří Fiala, Nikola Jedličková +2
The notion of graph covers (also referred to as locally bijective homomorphisms) plays an important role in topological graph theory and has found its computer science applications…
Computational Complexity of Covering Disconnected Multigraphs
Jan Bok, Jiří Fiala, Nikola Jedličková +2
The notion of graph covers is a discretization of covering spaces introduced and deeply studied in topology. In discrete mathematics and theoretical computer science, they have att…
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…