research
∙
05/16/2023
Decomposition of (infinite) digraphs along directed 1-separations
We introduce torsoids, a canonical structure in matching covered graphs,...
share
research
∙
02/06/2023
Tight bound on treedepth in terms of pathwidth and longest path
We show that every graph with pathwidth strictly less than a that contai...
research
∙
01/06/2023
Simpler and faster algorithms for detours in planar digraphs
In the directed detour problem one is given a digraph G and a pair of ve...
research
∙
07/15/2022
Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
We show fixed-parameter tractability of the Directed Multicut problem wi...
research
∙
06/18/2021
Graphs with at most two moplexes
A moplex is a natural graph structure that arises when lifting Dirac's c...
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
∙
08/05/2020
Constant Congestion Brambles
A bramble in an undirected graph G is a family of connected subgraphs of...
research
∙
08/10/2019
Avoidable paths in graphs
We prove a recent conjecture of Beisegel et al. that for every positive ...
research
∙
02/17/2019
Braces of Perfect Matching Width 2
A graph G is called matching covered if it is connected and every edge i...
research
∙
02/04/2019