research
∙
08/23/2023
Cliquewidth and dimension
We prove that every poset with bounded cliquewidth and with sufficiently...
share
research
∙
06/06/2023
Pathwidth vs cocircumference
The circumference of a graph G with at least one cycle is the length of ...
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
∙
02/24/2023
Neighborhood complexity of planar graphs
Reidl, Sánchez Villaamil, and Stravopoulos (2019) characterized graph cl...
research
∙
02/06/2023
Tight bound on treedepth in terms of pathwidth and longest path
We show that every graph with pathwidth strictly less than a that contai...
research
∙
12/21/2022
Edge separators for graphs excluding a minor
We prove that every n-vertex K_t-minor-free graph G of maximum degree Δ ...
research
∙
11/21/2022
Treedepth vs circumference
The circumference of a graph G is the length of a longest cycle in G, or...
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
∙
06/10/2021
Integer programs with bounded subdeterminants and two nonzeros per row
We give a strongly polynomial-time algorithm for integer linear programs...
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
∙
08/03/2020
Approximating pathwidth for graphs of small treewidth
We describe a polynomial-time algorithm which, given a graph G with tree...
research
∙
06/19/2020
Tight Bounds on The Clique Chromatic Number
The clique chromatic number of a graph is the minimum number of colours ...
research
∙
06/07/2020
Two lower bounds for p-centered colorings
Given a graph G and an integer p, a coloring f : V(G) →ℕ is p-centered i...
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
∙
03/09/2020
Adjacency Labelling for Planar Graphs (and Beyond)
We show that there exists an adjacency labelling scheme for planar graph...
research
∙
02/02/2020
Excluding a ladder
Which graph classes C exclude a fixed ladder as a minor? We show that th...
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
∙
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
∙
12/17/2019
Erdős-Pósa from ball packing
A classic theorem of Erdős and Pósa (1965) states that every graph has e...
research
∙
11/28/2019
Large independent sets in triangle-free cubic graphs: beyond planarity
Every n-vertex planar triangle-free graph with maximum degree at most 3 ...
research
∙
08/17/2019
The stable set problem in graphs with bounded genus and bounded odd cycle packing number
Consider the family of graphs without k node-disjoint odd cycles, where ...
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
∙
04/05/2019
Unavoidable minors for graphs with large ℓ_p-dimension
A metric graph is a pair (G,d), where G is a graph and d:E(G) →R_≥0 is a...
research
∙
02/18/2019
Information-theoretic lower bounds for quantum sorting
We analyze the quantum query complexity of sorting under partial informa...
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
∙
08/30/2018
Improved approximation algorithms for hitting 3-vertex paths
We study the problem of deleting a minimum cost set of vertices from a g...
research
∙
07/13/2018
A tight Erdős-Pósa function for planar minors
Let H be a planar graph. By a classical result of Robertson and Seymour,...
research
∙
04/17/2018
Progress on the adjacent vertex distinguishing edge colouring conjecture
A proper edge colouring of a graph is adjacent vertex distinguishing if ...
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
∙
10/17/2017
A tight Erdős-Pósa function for wheel minors
Let W_t denote the wheel on t+1 vertices. We prove that for every intege...
research
∙
08/17/2017