Clément Rambaud

Product structure of graphs excluding a topological minor

Jędrzej Hodor, Hoang La, Piotr Micek +1

We prove that, for all positive integers $h$ and $t$ and every graph $X$ with $td (X) \leq h$ , there exists a positive integer $c (X, t)$ such that every graph $G$ with $\mat…

Erdős-Pósa property of rooted tree minors

Quentin Claus, Gwenaël Joret, Clément Rambaud +1

Fiorini, Joret, and Wood (2013) showed that tree minors satisfy the so-called Erdős-Pósa property with a linear bound: For every tree $T$ there exists a constant $c \geq 1$ such th…

On the $(\leq p)$ -inversion diameter of oriented graphs

Frédéric Havet, Clément Rambaud, Caroline Silva

In an oriented graph $G$ , the {\it inversion} of a subset $X$ of vertices consists in reversing the orientation of all arcs with both endvertices in $X$ . The {\it $(\leq p)$ -…

Blow-up structure of graphs excluding a tree or an apex-tree as a minor

Quentin Claus, Gwenaël Joret, Clément Rambaud

We prove blow-up structure theorems for graphs excluding a tree or an apex-tree as a minor. First, we show that for every $t$ -vertex tree $T$ with $t \geq 3$ and radius $h$ , and eve…

Centered colorings and weak coloring numbers in minor-closed graph classes

Jędrzej Hodor, Hoang La, Piotr Micek +1

Let $C$ be a proper minor-closed class of graphs. Given the minors excluded in $C$ , we determine the maximum $q$ -centered chromatic number and the maximum $q$ th…

Cops and robber in graphs with bounded vertex cover number

Prosenjit Bose, Louis Esperet, Jędrzej Hodor +3

Meyniel's conjecture states that $n$ -vertex connected graphs have cop number $O (n)$ . The current best known upper bound is $n / 2^{(1 - o (1)) l o g n}$ , proved independentl…

math.CO2025

Making an oriented graph acyclic using inversions of bounded or prescribed size

Jørgen Bang-Jensen, Frédéric Havet, Florian Hörsch +3

Given an oriented graph $D$ , the inversion of a subset $X$ of vertices consists in reversing the orientation of all arcs with both endpoints in $X$ . When the subset $X$ is of size…

math.CO2025

Faithful universal graphs for minor-closed classes

Paul Bastide, Louis Esperet, Carla Groenland +3

It was proved by Huynh, Mohar, Šámal, Thomassen and Wood in 2021 that any countable graph containing every countable planar graph as a subgraph has an infinite clique minor. We pro…

math.CO2025

Excluding a rectangular grid

Clément Rambaud

For every positive integer $k$ , we define the $k$ -treedepth as the largest graph parameter $td_{k}$ satisfying (i) $td_{k} (\emptyset) = 0$ ; (ii) $\mathrm{td}_k(G) \leq…

Centered colorings in minor-closed graph classes

Jędrzej Hodor, Hoang La, Piotr Micek +1

A vertex coloring $φ$ of a graph $G$ is $p$ -centered if for every connected subgraph $H$ of $G$ , either $φ$ uses more than $p$ colors on $H$ , or there is a color that appears exact…

Blow-ups and extensions of trees in tournaments

Pierre Aboulker, Frédéric Havet, William Lochet +3

A class of acyclic digraphs $C$ is linearly unavoidable if there exists a constant $c$ such that every digraph $D \in C$ is contained in all tournaments of order…

Weak coloring numbers of minor-closed graph classes

Jędrzej Hodor, Hoang La, Piotr Micek +1

We study the growth rate of weak coloring numbers of graphs excluding a fixed graph as a minor. Van den Heuvel et al. (European J. of Combinatorics, 2017) showed that for a fixed g…

math.CO2024★ 1 cited

Diameter of the inversion graph

Frédéric Havet, Florian Hörsch, Clément Rambaud

In an oriented graph $G$ , the inversion of a subset $X$ of vertices consists in reversing the orientation of all arcs with both endvertices in $X$ . The inversion graph of a l…

Quickly excluding an apex-forest

Jędrzej Hodor, Hoang La, Piotr Micek +1

We give a short proof that for every apex-forest $X$ on at least two vertices, graphs excluding $X$ as a minor have layered pathwidth at most $2∣ V (X) ∣ - 3$ . This improves upon a resu…

Partitioning a Planar Graph into two Triangle-Forests

Kolja Knauer, Clément Rambaud, Torsten Ueckerdt

We show that the vertices of every planar graph can be partitioned into two sets, each inducing a so-called triangle-forest, i.e., a graph with no cycles of length more than three.…

Subdivisions in dicritical digraphs with large order or digirth

Lucas Picasarri-Arrieta, Clément Rambaud

Aboulker et al. proved that a digraph with large enough dichromatic number contains any fixed digraph as a subdivision. The dichromatic number of a digraph is the smallest order of…

The $χ$ -binding function of $d$ -directional segment graphs

Lech Duraj, Ross J. Kang, Hoang La +4

Given a positive integer $d$ , the class $d$ -DIR is defined as all those intersection graphs formed from a finite collection of line segments in $R^{2}$ having at most $d$ s…

The grid-minor theorem revisited

Vida Dujmović, Robert Hickingbotham, Jędrzej Hodor +6

We prove that for every planar graph $X$ of treedepth $h$ , there exists a positive integer $c$ such that for every $X$ -minor-free graph $G$ , there exists a graph $H$ of treewidth a…

On the minimum number of arcs in $4$ -dicritical oriented graphs

Frédéric Havet, Lucas Picasarri-Arrieta, Clément Rambaud

The dichromatic number $χ (D)$ of a digraph $D$ is the minimum number of colours needed to colour the vertices of a digraph such that each colour class induces an acyclic subdig…