research
∙
06/09/2023
Proof of the Clustered Hadwiger Conjecture
Hadwiger's Conjecture asserts that every K_h-minor-free graph is properl...
share
research
∙
04/04/2023
The structure of quasi-transitive graphs avoiding a minor with applications to the domino problem
An infinite graph is quasi-transitive if its vertex set has finitely man...
research
∙
06/06/2022
Optimal Adjacency Labels for Subgraphs of Cartesian Products
For any hereditary graph class ℱ, we construct optimal adjacency labelin...
research
∙
06/01/2022
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
A graph is O_k-free if it does not contain k pairwise vertex-disjoint an...
research
∙
02/18/2022
Sketching Distances in Monotone Graph Classes
We study the problems of adjacency sketching, small-distance sketching, ...
research
∙
02/01/2022
Testability and local certification of monotone properties in minor-closed classes
The main problem in the area of property testing is to understand which ...
research
∙
06/23/2021
Distributed coloring and the local structure of unit-disk graphs
Coloring unit-disk graphs efficiently is an important problem in the glo...
research
∙
02/08/2021
Local certification of graphs on surfaces
A proof labelling scheme for a graph class 𝒞 is an assignment of certifi...
research
∙
12/04/2020
Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces
The asymptotic dimension is an invariant of metric spaces introduced by ...
research
∙
12/03/2020
Optimal labelling schemes for adjacency, comparability and reachability
We construct asymptotically optimal adjacency labelling schemes for ever...
research
∙
12/03/2020
Distributed algorithms for fractional coloring
In this paper we study fractional coloring from the angle of distributed...
research
∙
10/12/2020
Sparse universal graphs for planarity
We show that for every integer n≥ 1 there exists a graph G_n with (1+o(1...
research
∙
03/09/2020
Adjacency Labelling for Planar Graphs (and Beyond)
We show that there exists an adjacency labelling scheme for planar graph...
research
∙
01/13/2020
Packing and covering balls in graphs excluding a minor
We prove that for every integer t> 1 there exists a constant c_t such th...
research
∙
04/10/2019
Planar graphs have bounded nonrepetitive chromatic number
A colouring of a graph is "nonrepetitive" if for every path of even orde...
research
∙
02/13/2019
Local approximation of the Maximum Cut in regular graphs
This paper is devoted to the distributed complexity of finding an approx...
research
∙
09/21/2018
Distributed coloring of graphs with an optimal number of colors
This paper studies sufficient conditions to obtain efficient distributed...
research
∙
03/29/2018
Least conflict choosability
Given a multigraph, suppose that each vertex is given a local assignment...
research
∙
02/15/2018
Distributed coloring in sparse graphs with fewer colors
This paper is concerned with efficiently coloring sparse graphs in the d...
research
∙
02/11/2018