research
∙
07/03/2023
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Dynamic programming on various graph decompositions is one of the most f...
share
research
∙
06/08/2023
Twin-width of subdivisions of multigraphs
For each d≤3, we construct a finite set F_d of multigraphs such that for...
research
∙
12/15/2022
Twin-width of random graphs
We investigate the twin-width of the Erdős-Rényi random graph G(n,p). We...
research
∙
08/17/2022
The proper conflict-free k-coloring problem and the odd k-coloring problem are NP-complete on bipartite graphs
A proper coloring of a graph is proper conflict-free if every non-isolat...
research
∙
10/08/2021
Bounds for the Twin-width of Graphs
Bonnet, Kim, Thomassé, and Watrigant (2020) introduced the twin-width of...
research
∙
08/02/2020
Tree pivot-minors and linear rank-width
Tree-width and its linear variant path-width play a central role for the...
research
∙
11/11/2019
A polynomial kernel for 3-leaf power deletion
A graph G is an ℓ-leaf power of a tree T if V(G) is equal to the set of ...
research
∙
11/01/2019
Obstructions for bounded shrub-depth and rank-depth
Shrub-depth and rank-depth are dense analogues of the tree-depth of a gr...
research
∙
09/12/2018
Classes of graphs with no long cycle as a vertex-minor are polynomially χ-bounded
A class G of graphs is χ-bounded if there is a function f such that for...
research
∙
11/04/2017