6 papers
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…
Generalizing Brooks' theorem via Partial Coloring is Hard Classically and Locally
Jan Bok, Avinandan Das, Anna Gujgiczer +1
We investigate the classical and distributed complexity of \emph{-partial -coloring} where , a natural generalization of Brooks' theorem where each vertex should be colo…
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…
On the expressive power of -edge-colourings of graphs
Jan Bok, Santiago Guzmán-Pro, Nikola JedliÄková +1
Given a finite set of -edge-coloured graphs and a hereditary property of graphs , we say that expresses if a graph has t…
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…
Resolving Sets in Temporal Graphs
Jan Bok, Antoine Dailly, Tuomo Lehtilä
A \emph{resolving set} in a graph is a set of vertices such that every vertex of is uniquely identified by its distances to the vertices of . Introduced in the 1970s…