4 papers
On a recolouring version of Hadwiger's conjecture
Marthe Bonamy, Marc Heinrich, Clément Legrand-Duchesne +1
We prove that for any , for any large enough , there is a graph that admits no -minor but admits a -colouring that is "frozen" wi…
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…
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…
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. R…