2 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…
cs.DS2025
An algorithmic Vizing's theorem: toward efficient edge-coloring sampling with an optimal number of colors
Lucas De Meyer, František Kardoš, Aurélie Lagoutte +1
The problem of sampling edge-colorings of graphs with maximum degree has received considerable attention and efficient algorithms are available when the number of colors is lar…