Clément Legrand-Duchesne

activity

20212025

collaborators

6 papers

math.CO2025

A Recolouring Version of a Conjecture of Reed

Lucas De Meyer, Clément Legrand-Duchesne, Jared León +2

Reed conjectured that the chromatic number of any graph is closer to its clique number than to its maximum degree plus one. We consider a recolouring version of this conjecture, wi…

math.CO2025

Reconfiguration of square-tiled surfaces

Vincent Delecroix, Clément Legrand-Duchesne

We consider a combinatorial reconfiguration problem on a subclass of quadrangulations of surfaces called square-tiled surfaces. Our elementary move is a shear in a cylinder that co…

math.CO2024

Random embeddings of bounded degree trees with optimal spread

Paul Bastide, Clément Legrand-Duchesne, Alp Müyesser

A seminal result of Komlós, Sárközy, and Szemerédi states that any n-vertex graph G with minimum degree at least (1/2 + α)n contains every n-vertex tree T of bounded degree. Recent…

math.CO2022

Strengthening a theorem of Meyniel

Quentin Deschamps, Carl Feghali, František Kardoš +2

For an integer $k \geq 1$ and a graph $G$ , let $K_{k} (G)$ be the graph that has vertex set all proper $k$ -colorings of $G$ , and an edge between two vertices $α$ and~ $β$ whe…

math.CO2021

Kempe changes in degenerate graphs

Marthe Bonamy, Vincent Delecroix, Clément Legrand-Duchesne

We consider Kempe changes on the $k$ -colorings of a graph on $n$ vertices. If the graph is $(k - 1)$ -degenerate, then all its $k$ -colorings are equivalent up to Kempe changes. Howeve…

math.CO2021

On a recolouring version of Hadwiger's conjecture

Marthe Bonamy, Marc Heinrich, Clément Legrand-Duchesne +1

We prove that for any $ε > 0$ , for any large enough $t$ , there is a graph $G$ that admits no $K_{t}$ -minor but admits a $(\frac{3}{2} - ε) t$ -colouring that is "frozen" wi…