Lucas de Meyer

collaborators

4 papers

math.CO2026

Optimal List Recoloring of Subcubic Graphs and Complete Multipartite Graphs

Lucas De Meyer

For a list-assignment $L$ , the reconfiguration graph $C_{L} (G)$ of a graph $G$ is the graph whose vertices are proper $L$ -colorings of $G$ and whose edges link two colorings that dif…

math.CO2026

A polynomial bound on the pathwidth of graphs edge-coverable by $k$ shortest paths

Julien Baste, Lucas De Meyer, Ugo Giocanti +2

Dumas, Foucaud, Perez and Todinca (2024) recently proved that every graph whose edges can be covered by $k$ shortest paths has pathwidth at most $O (3^{k})$ . In this paper, we improve…

math.CO2025

A Recolouring Version of a Conjecture of Reed

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…

cs.DS2025

An algorithmic Vizing's theorem: toward efficient edge-coloring sampling with an optimal number of colors

The problem of sampling edge-colorings of graphs with maximum degree $I^$ has received considerable attention and efficient algorithms are available when the number of colors is la…

Optimal List Recoloring of Subcubic Graphs and Complete Multipartite Graphs

A polynomial bound on the pathwidth of graphs edge-coverable by k shortest paths

A Recolouring Version of a Conjecture of Reed

An algorithmic Vizing's theorem: toward efficient edge-coloring sampling with an optimal number of colors

A polynomial bound on the pathwidth of graphs edge-coverable by $k$ shortest paths