research
∙
09/17/2023
Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number
A Hamiltonian path (a Hamiltonian cycle) in a graph is a path (a cycle, ...
share
research
∙
06/10/2023
List homomorphisms to separable signed graphs
The complexity of the list homomorphism problem for signed graphs appear...
research
∙
06/10/2023
Computational Complexity of Covering Disconnected Multigraphs
The notion of graph covers is a discretization of covering spaces introd...
research
∙
06/02/2022
Min orderings and list homomorphism dichotomies for signed and unsigned graphs
The CSP dichotomy conjecture has been recently established, but a number...
research
∙
04/08/2022
List covering of regular multigraphs
A graph covering projection, also known as a locally bijective homomorph...
research
∙
03/28/2021
Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges
We initiate the study of computational complexity of graph coverings, ak...
research
∙
08/21/2020
Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs
A k-colouring c of a graph G is a mapping V(G) to 1,2,... k such that c(...
research
∙
05/12/2020
List homomorphism problems for signed graphs
We consider homomorphisms of signed graphs from a computational perspect...
research
∙
11/24/2019
A relaxed version of Šoltés's problem and cactus graphs
The Wiener index is a graph parameter originating from chemical graph th...
research
∙
01/15/2019
On Extremal Graphs of Weighted Szeged Index
An extension of the well-known Szeged index was introduced recently, nam...
research
∙
11/09/2018
A note on simultaneous representation problem for interval and circular-arc graphs
In this short note, we show two NP-completeness results regarding the si...
research
∙
04/15/2018