Clément Legrand-Duchesne

activity

20212026

collaborators

6 papers

math.CO2026

Dirac's theorem and the switch geometry of perfect matchings

Ross J. Kang, Clément Legrand-Duchesne

Let $G$ be a graph on an even number $n$ of vertices and let $M_{G}$ be the collection of perfect matchings in $G$ . Dirac's theorem says that if the minimum degree $δ (G)$ of $…

math.CO2026

A Gray code for arborescences of tournaments

Marthe Bonamy, Michael Hoffmann, Clément Legrand-Duchesne +1

We consider the following question of Knuth: given a directed graph $G$ and a root $r$ , can the arborescences of $G$ rooted in $r$ be listed such that any two consecutive arboresce…

math.CO2026

A coarse Gallai theorem

Marc Distel, Ugo Giocanti, Jędrzej Hodor +2

We prove that there exist functions $f$ and $g$ such that for all positive integers $k$ and $d$ , for every graph $G$ and every subset $A$ of the vertices of $G$ , either $G$ contain…

cs.CC2023

Minimum Separator Reconfiguration

Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud +4

We study the problem of reconfiguring one minimum $s$ - $t$ -separator $A$ into another minimum $s$ - $t$ -separator $B$ in some $n$ -vertex graph $G$ containing two non-adjacent vertices…

math.CO2023

The structure of quasi-transitive graphs avoiding a minor with applications to the domino problem

Louis Esperet, Ugo Giocanti, Clément Legrand-Duchesne

An infinite graph is quasi-transitive if its vertex set has finitely many orbits under the action of its automorphism group. In this paper we obtain a structure theorem for locally…

cs.CC2021

Parameterized complexity of untangling knots

Clément Legrand-Duchesne, Ashutosh Rai, Martin Tancer

Deciding whether a diagram of a knot can be untangled with a given number of moves (as a part of the input) is known to be NP-complete. In this paper we determine the parameterized…