1 citations · 1 across the 1 of their papers we have counts for
9 papers
Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
Fedor V. Fomin, Petr A. Golovach, Nikola JedliÄková +3
The classic theorem of Gallai and Milgram (1960) generalizes several fundamental results in Graph Theory, such as Dilworth's theorem on posets and KÅnig's theorem on matchings in…
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…
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…
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…
Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number
Nikola JedliÄková, Jan KratochvÃl
A Hamiltonian path (a Hamiltonian cycle) in a graph is a path (a cycle, respectively) that traverses all of its vertices. The problems of deciding their existence in an input graph…