research
∙
05/08/2023
The induced two paths problem
We give an approximate Menger-type theorem for when a graph G contains t...
share
research
∙
12/12/2022
Aharoni's rainbow cycle conjecture holds up to an additive constant
In 2017, Aharoni proposed the following generalization of the Caccetta-H...
research
∙
11/15/2022
Notes on Aharoni's rainbow cycle conjecture
In 2017, Ron Aharoni made the following conjecture about rainbow cycles ...
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
∙
06/24/2021
Slack matrices, k-products, and 2-level polytopes
In this paper, we study algorithmic questions concerning products of mat...
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/25/2021
On the Erdős-Pósa property for long holes in C_4-free graphs
We prove that there exists a function f(k)=𝒪(k^2 log k) such that for ev...
research
∙
09/23/2020
A simple (2+ε)-approximation algorithm for Split Vertex Deletion
A split graph is a graph whose vertex set can be partitioned into a cliq...
research
∙
08/20/2020
A simple 7/3-approximation algorithm for feedback vertex set in tournaments
We show that performing just one round of the Sherali-Adams hierarchy gi...
research
∙
07/16/2020
A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem
We give the first 2-approximation algorithm for the cluster vertex delet...
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
∙
02/06/2020
Recognizing Cartesian products of matrices and polytopes
The 1-product of matrices S_1 ∈R^m_1 × n_1 and S_2 ∈R^m_2 × n_2 is the m...
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
∙
12/02/2019
Idealness of k-wise intersecting families
A clutter is k-wise intersecting if every k members have a common elemen...
research
∙
11/27/2019
Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
Let G be an n-node graph without two disjoint odd cycles. The algorithm ...
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/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/16/2019
Flip distances between graph orientations
Flip graphs are a ubiquitous class of graphs, which encode relations ind...
research
∙
11/08/2018
The biclique covering number of grids
We determine the exact value of the biclique covering number for all gri...
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
∙
06/03/2018
Short rainbow cycles in sparse graphs
Let G be a simple n-vertex graph and c be a colouring of E(G) with n col...
research
∙
06/01/2018
Extension Complexity of the Correlation Polytope
We prove that for every n-vertex graph G, the extension complexity of th...
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
∙
11/03/2017
Strengthening Convex Relaxations of 0/1-Sets Using Boolean Formulas
In convex integer programming, various procedures have been developed to...
research
∙
10/17/2017