research
∙
07/04/2023
Sparse Graphs of Twin-width 2 Have Bounded Tree-width
Twin-width is a structural width parameter introduced by Bonnet, Kim, Th...
share
research
∙
01/31/2023
Flipper games for monadically stable graph classes
A class of graphs 𝒞 is monadically stable if for any unary expansion 𝒞 o...
research
∙
06/16/2022
Twin-width and types
We study problems connected to first-order logic in graphs of bounded tw...
research
∙
05/02/2022
Taming graphs with no large creatures and skinny ladders
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: i...
research
∙
02/25/2022
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
We present a fixed-parameter tractable algorithm for first-order model c...
research
∙
01/26/2022
Treelike decompositions for transductions of sparse graphs
We give new decomposition theorems for classes of graphs that can be tra...
research
∙
07/08/2021
Stable graphs of bounded twin-width
We prove that every class of graphs 𝒞 that is monadically stable and has...
research
∙
07/22/2020
Differential games, locality and model checking for FO logic of graphs
We introduce differential games for FO logic of graphs, a variant of Ehr...
research
∙
10/04/2018
First-order interpretations of bounded expansion classes
The notion of bounded expansion captures uniform sparsity of graph class...
research
∙
05/04/2018
A New Perspective on FO Model Checking of Dense Graph Classes
We study the first-order (FO) model checking problem of dense graphs, na...
research
∙
09/28/2017