Showing cs.DMShow all
3 papers · 1 filter
cs.DM2025
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…
cs.DM2025
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…
cs.DM2025
Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
Laurent Beaudou, Jan Bok, Florent Foucaud +2
The \emph{-neighbourhood complexity} of a graph is the function counting, for a given integer , the largest possible number, over all vertex-subsets of size , of s…