Showing cs.DMShow all
3 papers · 1 filter
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…
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…