4 papers
Nowhere-zero flow reconfiguration
Louis Esperet, Kevin Hendrey, Aurélie Lagoutte +3
We initiate the study of nowhere-zero flow reconfiguration. The natural question is whether any two nowhere-zero -flows of a given graph are connected by a sequence of nowhe…
Local certification of geometric graph classes
Oscar Defrain, Louis Esperet, Aurélie Lagoutte +2
The goal of local certification is to locally convince the vertices of a graph that satisfies a given property. A prover assigns short certificates to the vertices of the g…
The Canadian Traveller Problem on outerplanar graphs
Laurent Beaudou, Pierre Bergé, Vsevolod Chernyshev +5
We study the -Canadian Traveller Problem, where a weighted graph with a source and a target are given. This problem also has a hidden input $E_* \…
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 la…