research
∙
06/30/2023
Subexponential parameterized algorithms for cycle-hitting problems in contact and intersection graphs of segments
In this paper we investigate the existence of subexponential parameteriz...
share
research
∙
04/19/2023
Sparse graphs without long induced paths
Graphs of bounded degeneracy are known to contain induced paths of order...
research
∙
08/30/2022
Lower bound for constant-size local certification
Given a network property or a data structure, a local certification is a...
research
∙
01/11/2022
Long induced paths in minor-closed graph classes and beyond
In this paper we show that every graph of pathwidth less than k that has...
research
∙
10/01/2018
Enumerating minimal dominating sets in triangle-free graphs
It is a long-standing open problem whether the minimal dominating sets o...
research
∙
08/02/2018
Lean tree-cut decompositions: obstructions and algorithms
The notion of tree-cut width has been introduced by Wollan [The structur...
research
∙
07/13/2018
A tight Erdős-Pósa function for planar minors
Let H be a planar graph. By a classical result of Robertson and Seymour,...
research
∙
03/20/2018
Packing and covering induced subdivisions
A graph class F has the induced Erdős-Pósa property if there exists a fu...
research
∙
10/17/2017
A tight Erdős-Pósa function for wheel minors
Let W_t denote the wheel on t+1 vertices. We prove that for every intege...
research
∙
09/27/2017