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...
share
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
∙
07/14/2022
Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
Let ℱ be a family of graphs, and let p,r be nonnegative integers. The (p...
research
∙
10/08/2021
Bounds for the Twin-width of Graphs
Bonnet, Kim, Thomassé, and Watrigant (2020) introduced the twin-width of...
research
∙
09/02/2020
Towards constant-factor approximation for chordal / distance-hereditary vertex deletion
For a family of graphs ℱ, Weighted ℱ-Deletion is the problem for which t...
research
∙
02/25/2020
Well-partitioned chordal graphs: obstruction set and disjoint paths
We introduce a new subclass of chordal graphs that generalizes split gra...
research
∙
11/11/2019