Jean-Florent Raymond

activity

20132026

most citedPolynomial expansion and sublinear separators

15 citations · 56 across the 16 of their papers we have counts for

collaborators

26 papers

math.CO2026

An improved bound on the treewidth of planar graphs excluding a grid minor

Wouter Cames van Batenburg, Quentin Claus, Gwenaël Joret +3

We show that every planar graph with no $t \times t$ grid minor has treewidth at most $4 t + 4$ . This improves on the previously best known bound of $\frac{9}{2} t - \frac{11}{2}$ , du…

math.CO2023

Sparse graphs without long induced paths

Oscar Defrain, Jean-Florent Raymond

Graphs of bounded degeneracy are known to contain induced paths of order $Ω (lo g lo g n)$ when they contain a path of order $n$ , as proved by Nešetřil and Ossona de Mendez (2012).…

cs.DC2022★ 1 cited

Lower bound for constant-size local certification

Virgina Ardévol Martínez, Marco Caoduro, Laurent Feuilloley +3

Given a network property or a data structure, a local certification is a labeling that allows to efficiently check that the property is satisfied, or that the structure is correct.…

cs.DM2022

Long induced paths in minor-closed graph classes and beyond

Claire Hilaire, Jean-Florent Raymond

In this paper we show that every graph of pathwidth less than $k$ that has a path of order $n$ also has an induced path of order at least $\frac{1}{3} n^{1/ k}$ . This is an exponent…

math.CO2021

Twin-width and generalized coloring numbers

Jan Dreier, Jakub Gajarsky, Yiting Jiang +2

In this paper, we prove that a graph $G$ with no $K_{s, s}$ -subgraph and twin-width $d$ has $r$ -admissibility and $r$ -coloring numbers bounded from above by an exponential function…

cs.DM2018

Enumerating minimal dominating sets in $K_{t}$ -free graphs and variants

Marthe Bonamy, Oscar Defrain, Marc Heinrich +2

It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we investigate this problem in graph cl…

math.CO2018

A Menger-like property of tree-cut width

Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond +1

In 1990, Thomas proved that every graph admits a tree decomposition of minimum width that additionally satisfies a certain vertex-connectivity condition called leanness [A Menger-l…

math.CO2018★ 8 cited

A tight Erdős-Pósa function for planar minors

Wouter Cames van Batenburg, Tony Huynh, Gwenaël Joret +1

Let $H$ be a planar graph. By a classical result of Robertson and Seymour, there is a function $f : N \to R$ such that for all $k \in N$ and all graphs $G$ …

cs.DM2018

Packing and covering induced subdivisions

O-joung Kwon, Jean-Florent Raymond

A class $F$ of graphs has the induced Erdős-Pósa property if there exists a function $f$ such that for every graph $G$ and every positive integer $k$ , $G$ contains either…

cs.DM2017★ 2 cited

A tight Erdős-Pósa function for wheel minors

Pierre Aboulker, Samuel Fiorini, Tony Huynh +3

Let $W_{t}$ denote the wheel on $t + 1$ vertices. We prove that for every integer $t \geq 3$ there is a constant $c = c (t)$ such that for every integer $k \geq 1$ and every graph $G$ , eit…

cs.DS2017

On the tractability of optimization problems on H-graphs

Fedor V. Fomin, Petr A. Golovach, Jean-Florent Raymond

For a graph $H$ , a graph $G$ is an $H$ -graph if it is an intersection graph of connected subgraphs of some subdivision of $H$ . $H$ -graphs naturally generalize several important gra…

math.CO2017★ 15 cited

Polynomial expansion and sublinear separators

Louis Esperet, Jean-Florent Raymond

Let $C$ be a class of graphs that is closed under taking subgraphs. We prove that if for some fixed $0 < δ \leq 1$ , every $n$ -vertex graph of $C$ has a balanced sep…

cs.DS2016★ 12 cited

Linear kernels for edge deletion problems to immersion-closed graph classes

Archontia C. Giannopoulou, Michał Pilipczuk, Dimitrios M. Thilikos +2

Suppose $F$ is a finite family of graphs. We consider the following meta-problem, called $F$ -Immersion Deletion: given a graph $G$ and integer $k$ , decide wheth…

cs.DS2016

Cutwidth: obstructions and algorithmic aspects

Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond +2

Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges betw…

math.AG2016★ 9 cited

Conic bundles that are not birational to numerical Calabi--Yau pairs

János Kollár

Let $X$ be a general conic bundle over the projective plane with branch curve of degree at least 19. We prove that there is no normal projective variety $Y$ that is birational to $…

math.CO2016★ 3 cited

Packing and Covering Immersion Models of Planar subcubic Graphs

Archontia Giannopoulou, O-joung Kwon, Jean-Florent Raymond +1

A graph $H$ is an immersion of a graph $G$ if $H$ can be obtained by some sugraph $G$ after lifting incident edges. We prove that there is a polynomial function $f:\Bbb{N}\times\Bb…

cs.DM2016

Recent techniques and results on the Erdős-Pósa property

Jean-Florent Raymond, Dimitrios M. Thilikos

Several min-max relations in graph theory can be expressed in the framework of the Erdős-Pósa property. Typically, this property reveals a connection between packing and covering p…

math.CO2016★ 2 cited

Well-quasi-ordering H-contraction-free graphs

Marcin Kamiński, Jean-Florent Raymond, Théophile Trunck

A well-quasi-order is an order which contains no infinite decreasing sequence and no infinite collection of incomparable elements. In this paper, we consider graph classes defined…

math.CO2015

Induced minors and well-quasi-ordering

Jarosław Błasiok, Marcin Kamiński, Jean-Florent Raymond +1

A graph $H$ is an induced minor of a graph $G$ if it can be obtained from an induced subgraph of $G$ by contracting edges. Otherwise, $G$ is said to be $H$ -induced minor-free. Robi…

cs.DS2015

An $O (lo g O P T)$ -approximation for covering and packing minor models of $θ_{r}$

Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau +1

Given two graphs $G$ and $H$ , we define $v-cover_{H} (G)$ (resp. $e-cover_{H} (G)$ ) as the minimum number of vertices (resp. edges) whose removal from $G$ produces…

math.CO2015

Minors in graphs of large $θ_{r}$ -girth

Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau +1

For every $r \in N$ , let $θ_{r}$ denote the graph with two vertices and $r$ parallel edges. The $θ_{r}$ -girth of a graph $G$ is the minimum number of edges of a subgraph of $G…

math.CO2014

Multigraphs without large bonds are wqo by contraction

Marcin Kamiński, Jean-Florent Raymond, Théophile Trunck

We show that the class of multigraphs with at most $p$ connected components and bonds of size at most $k$ is well-quasi-ordered by edge contraction for all positive integers $p, k$ .…

cs.DM2014

Scattered packings of cycles

Aistis Atminas, Marcin Kamiński, Jean-Florent Raymond

We consider the problem Scattered Cycles which, given a graph $G$ and two positive integers $r$ and $ℓ$ , asks whether $G$ contains a collection of $r$ cycles that are pairwise a…

math.CO2013

An edge variant of the Erdős-Pósa property

Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos

For every $r \in N$ , we denote by $θ_{r}$ the multigraph with two vertices and $r$ parallel edges. Given a graph $G$ , we say that a subgraph $H$ of $G$ is a model of $θ_{r}…