research
∙
07/06/2023
The grid-minor theorem revisited
We prove that for every planar graph X of treedepth h, there exists a po...
share
research
∙
06/09/2023
Proof of the Clustered Hadwiger Conjecture
Hadwiger's Conjecture asserts that every K_h-minor-free graph is properl...
research
∙
03/27/2023
The Excluded Tree Minor Theorem Revisited
We prove that for every tree T of radius h, there is an integer c such t...
research
∙
08/22/2022
Product structure of graph classes with strongly sublinear separators
We investigate the product structure of hereditary graph classes admitti...
research
∙
07/14/2022
2-Layer Graph Drawings with Bounded Pathwidth
We determine which properties of 2-layer drawings characterise bipartite...
research
∙
06/06/2022
Product structure of graph classes with bounded treewidth
We show that many graphs with bounded treewidth can be described as subg...
research
∙
02/24/2022
Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
In a reduction sequence of a graph, vertices are successively identified...
research
∙
02/10/2022
Three-dimensional graph products with unbounded stack-number
We prove that the stack-number of the strong product of three n-vertex p...
research
∙
07/31/2021
An improved planar graph product structure theorem
Dujmović, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved th...
research
∙
06/22/2021
Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
Let G be a connected n-vertex graph in a proper minor-closed class 𝒢. We...
research
∙
05/04/2021
Separating layered treewidth and row treewidth
Layered treewidth and row treewidth are recently introduced graph parame...
research
∙
11/09/2020
Stack-number is not bounded by queue-number
We describe a family of graphs with queue-number at most 4 but unbounded...
research
∙
09/04/2020
Nonrepetitive graph colouring
A vertex colouring of a graph G is "nonrepetitive" if G contains no path...
research
∙
03/30/2020
Subgraph densities in a surface
Given a fixed graph H that embeds in a surface Σ, what is the maximum nu...
research
∙
02/13/2020
Notes on Tree- and Path-chromatic Number
Tree-chromatic number is a chromatic version of treewidth, where the cos...
research
∙
01/24/2020
Notes on Graph Product Structure Theory
It was recently proved that every planar graph is a subgraph of the stro...
research
∙
08/14/2019
Clustered Variants of Hajós' Conjecture
Hajós conjectured that every graph containing no subdivision of the comp...
research
∙
07/11/2019
The structure of k-planar graphs
Dujmović et al. (FOCS 2019) recently proved that every planar graph is a...
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
∙
04/09/2019
Planar Graphs have Bounded Queue-Number
We show that planar graphs have bounded queue-number, thus proving a con...
research
∙
01/17/2019
Queue Layouts of Graphs with Bounded Degree and Bounded Genus
We prove that graphs with bounded degree and bounded Euler genus have bo...
research
∙
10/19/2018
Minor-closed graph classes with bounded layered pathwidth
We prove that a minor-closed class of graphs has bounded layered pathwid...
research
∙
07/31/2018
Tight Upper Bounds on the Crossing Number in a Minor-Closed Class
The crossing number of a graph is the minimum number of crossings in a d...
research
∙
06/19/2018
Defective and Clustered Choosability of Sparse Graphs
An (improper) graph colouring has "defect" d if each monochromatic subgr...
research
∙
06/19/2018
Defective and Clustered Colouring of Sparse Graphs
An (improper) graph colouring has "defect" d if each monochromatic subgr...
research
∙
04/09/2018
Better bounds for poset dimension and boxicity
We prove that the dimension of every poset whose comparability graph has...
research
∙
04/03/2018
The exact chromatic number of the convex segment disjointness graph
Let P be a set of n points in strictly convex position in the plane. Let...
research
∙
01/05/2018
Seymour's conjecture on 2-connected graphs of large pathwidth
We prove the conjecture of Seymour (1993) that for every apex-forest H_1...
research
∙
08/16/2017