research
∙
06/03/2023
Subchromatic numbers of powers of graphs with excluded minors
A k-subcolouring of a graph G is a function f:V(G) →{0,…,k-1} such that ...
share
research
∙
09/24/2022
Twin-width V: linear minors, modular counting, and matrix multiplication
We continue developing the theory around the twin-width of totally order...
research
∙
09/15/2022
Decomposition horizons: from graph sparsity to model-theoretic dividing lines
Let 𝒞 be a hereditary class of graphs. Assume that for every p there is ...
research
∙
08/30/2022
On the first-order transduction quasiorder of hereditary classes of graphs
Logical transductions provide a very useful tool to encode classes of st...
research
∙
07/06/2022
Distributed domination on sparse graph classes
We show that the dominating set problem admits a constant factor approxi...
research
∙
03/31/2022
Transducing paths in graph classes with unbounded shrubdepth
Transductions are a general formalism for expressing transformations of ...
research
∙
05/08/2021
On set systems definable in sparse graph classes, discrepancy, and quantifier elimination
We study the (hereditary) discrepancy of definable set systems, which is...
research
∙
02/13/2021
Twin-width and permutations
Inspired by a width invariant defined on permutations by Guillemot and M...
research
∙
02/05/2021
Twin-width IV: low complexity matrices
We establish a list of characterizations of bounded twin-width for hered...
research
∙
10/06/2020
Towards an arboretum of monadically stable classes of graphs
Logical transductions provide a very useful tool to encode classes of st...
research
∙
07/15/2020
Rankwidth meets stability
We study two notions of being well-structured for classes of graphs that...
research
∙
03/26/2020
Regular partitions of gentle graphs
Szemeredi's Regularity Lemma is a very useful tool of extremal combinato...
research
∙
03/07/2020
Clustering powers of sparse graphs
We prove that if G is a sparse graph — it belongs to a fixed class of bo...
research
∙
11/15/2019
Linear rankwidth meets stability
Classes with bounded rankwidth are MSO-transductions of trees and classe...
research
∙
09/04/2019
Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
Classes with bounded rankwidth are MSO-transductions of trees and classe...
research
∙
12/18/2018
Model-Checking on Ordered Structures
We study the model-checking problem for first- and monadic second-order ...
research
∙
10/04/2018
First-order interpretations of bounded expansion classes
The notion of bounded expansion captures uniform sparsity of graph class...
research
∙
08/17/2017