research
∙
11/28/2022
On digraphs without onion star immersions
The t-onion star is the digraph obtained from a star with 2t leaves by r...
share
research
∙
10/13/2022
The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
The generic homomorphism problem, which asks whether an input graph G ad...
research
∙
05/26/2022
Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws
For graphs G and H, an H-coloring of G is an edge-preserving mapping fro...
research
∙
03/09/2022
Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
We revisit recent developments for the Maximum Weight Independent Set pr...
research
∙
02/17/2022
Computing list homomorphisms in geometric intersection graphs
A homomorphism from a graph G to a graph H is an edge-preserving mapping...
research
∙
05/20/2021
Tuza's Conjecture for Threshold Graphs
Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjo...
research
∙
03/26/2021
On objects dual to tree-cut decompositions
Tree-cut width is a graph parameter introduced by Wollan that is an anal...
research
∙
10/22/2020
Vertex deletion into bipartite permutation graphs
A permutation graph can be defined as an intersection graph of segments ...
research
∙
10/07/2020
Complexity of the list homomorphism problem in hereditary graph classes
A homomorphism from a graph G to a graph H is an edge-preserving mapping...
research
∙
09/27/2020
The Complexity of Connectivity Problems in Forbidden-Transition Graphs and Edge-Colored Graphs
The notion of forbidden-transition graphs allows for a robust generaliza...
research
∙
09/17/2020
Sparsification Lower Bounds for List H-Coloring
We investigate the List H-Coloring problem, the generalization of graph ...
research
∙
06/19/2020
Full complexity classification of the list homomorphism problem for bounded-treewidth graphs
A homomorphism from a graph G to a graph H is an edge-preserving mapping...
research
∙
10/02/2019
Subexponential-time algorithms for finding large induced sparse subgraphs
Let C and D be hereditary graph classes. Consider the following problem:...
research
∙
06/19/2019
Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
For graphs G and H, a homomorphism from G to H is an edge-preserving map...
research
∙
09/25/2018
Subexponential algorithms for variants of homomorphism problem in string graphs
We consider the complexity of finding weighted homomorphisms from inters...
research
∙
04/27/2018