
Smaller extended formulations for spanning tree polytopes in minorclosed classes and beyond
Let G be a connected nvertex graph in a proper minorclosed class 𝒢. We...
read it

Integer programs with bounded subdeterminants and two nonzeros per row
We give a strongly polynomialtime algorithm for integer linear programs...
read it

Sparse universal graphs for planarity
We show that for every integer n≥ 1 there exists a graph G_n with (1+o(1...
read it

Approximating pathwidth for graphs of small treewidth
We describe a polynomialtime algorithm which, given a graph G with tree...
read it

Tight Bounds on The Clique Chromatic Number
The clique chromatic number of a graph is the minimum number of colours ...
read it

Two lower bounds for pcentered colorings
Given a graph G and an integer p, a coloring f : V(G) →ℕ is pcentered i...
read it

Subgraph densities in a surface
Given a fixed graph H that embeds in a surface Σ, what is the maximum nu...
read it

Adjacency Labelling for Planar Graphs (and Beyond)
We show that there exists an adjacency labelling scheme for planar graph...
read it

Excluding a ladder
Which graph classes C exclude a fixed ladder as a minor? We show that th...
read it

Notes on Graph Product Structure Theory
It was recently proved that every planar graph is a subgraph of the stro...
read it

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...
read it

ErdősPósa from ball packing
A classic theorem of Erdős and Pósa (1965) states that every graph has e...
read it

Large independent sets in trianglefree cubic graphs: beyond planarity
Every nvertex planar trianglefree graph with maximum degree at most 3 ...
read it

The stable set problem in graphs with bounded genus and bounded odd cycle packing number
Consider the family of graphs without k nodedisjoint odd cycles, where ...
read it

Planar graphs have bounded nonrepetitive chromatic number
A colouring of a graph is "nonrepetitive" if for every path of even orde...
read it

Planar Graphs have Bounded QueueNumber
We show that planar graphs have bounded queuenumber, thus proving a con...
read it

Unavoidable minors for graphs with large ℓ_pdimension
A metric graph is a pair (G,d), where G is a graph and d:E(G) →R_≥0 is a...
read it

Informationtheoretic lower bounds for quantum sorting
We analyze the quantum query complexity of sorting under partial informa...
read it

Minorclosed graph classes with bounded layered pathwidth
We prove that a minorclosed class of graphs has bounded layered pathwid...
read it

Improved approximation algorithms for hitting 3vertex paths
We study the problem of deleting a minimum cost set of vertices from a g...
read it

A tight ErdősPósa function for planar minors
Let H be a planar graph. By a classical result of Robertson and Seymour,...
read it

Progress on the adjacent vertex distinguishing edge colouring conjecture
A proper edge colouring of a graph is adjacent vertex distinguishing if ...
read it

Seymour's conjecture on 2connected graphs of large pathwidth
We prove the conjecture of Seymour (1993) that for every apexforest H_1...
read it

A tight ErdősPósa function for wheel minors
Let W_t denote the wheel on t+1 vertices. We prove that for every intege...
read it

Nowhere Dense Graph Classes and Dimension
Nowhere dense graph classes provide one of the least restrictive notions...
read it
Gwenaël Joret
is this you? claim profile