7 citations · 23 across the 17 of their papers we have counts for
19 papers
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…
On the Structure of Hamiltonian Graphs with Small Independence Number
Nikola Jedličková, Jan Kratochvíl
A Hamiltonian path (cycle) in a graph is a path (cycle, respectively) which passes through all of its vertices. The problems of deciding the existence of a Hamiltonian cycle (path)…
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 b…
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…
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…
List homomorphisms to separable signed graphs
Jan Bok, Richard Brewster, Tomás Feder +2
The complexity of the list homomorphism problem for signed graphs appears difficult to classify. Existing results focus on special classes of signed graphs, such as trees and refle…
Min orderings and list homomorphism dichotomies for signed and unsigned graphs
Jan Bok, Richard Brewster, Pavol Hell +2
The CSP dichotomy conjecture has been recently established, but a number of other dichotomy questions remain open, including the dichotomy classification of list homomorphism probl…
List covering of regular multigraphs with semi-edges
Jan Bok, Jiří Fiala, Nikola Jedličková +2
In line with the recent development in topological graph theory, we are considering undirected graphs that are allowed to contain {\em multiple edges}, {\em loops}, and {\em semi-e…
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…
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…
List homomorphism problems for signed trees
Jan Bok, Richard Brewster, Tomás Feder +2
We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph $…
A relaxed version of Šoltés's problem and cactus graphs
Jan Bok, Nikola Jedličková, Jana Maxová
The \emph{Wiener index} is one of the most widely studied parameters in chemical graph theory. It is defined as the sum of the lengths of the shortest paths between all unordered p…
Maximum Wiener index of unicyclic graphs with given bipartition
Jan Bok, Nikola Jedličková, Jana Maxová
The \emph{Wiener index} is a widely studied topological index of graphs. One of the main problems in the area is to determine which graphs of given properties attain the extremal v…
On Extremal Graphs of Weighted Szeged Index
Jan Bok, Boris Furtula, Nikola Jedličková +1
An extension of the well-known Szeged index was introduced recently, named as weighted Szeged index (). This paper is devoted to characterizing the extremal trees a…
A note on simultaneous representation problem for interval and circular-arc graphs
Jan Bok, Nikola Jedličková
In this short note, we show two NP-completeness results regarding the \emph{simultaneous representation problem}, introduced by Lubiw and Jampani. The simultaneous representation p…
Edge-sum distinguishing labeling
Jan Bok, Nikola Jedličková
We study \emph{edge-sum distinguishing labeling}, a type of labeling recently introduced by Tuza in [Zs. Tuza, \textit{Electronic Notes in Discrete Mathematics} 60, (2017), 61-68]…