23 citations · 150 across the 51 of their papers we have counts for
8 papers · 1 filter
Kempe changes in degenerate graphs
Marthe Bonamy, Vincent Delecroix, Clément Legrand-Duchesne
We consider Kempe changes on the -colorings of a graph on vertices. If the graph is -degenerate, then all its -colorings are equivalent up to Kempe changes. Howeve…
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet +6
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Cliq…
Improved pyrotechnics : Closer to the burning graph conjecture
Paul Bastide, Marthe Bonamy, Anthony Bonato +4
The Burning Number Conjecture claims that for every connected graph of order its burning number satisfies While the conjecture remains o…
Gallai's path decomposition in planar graphs
Alexandre Blanché, Marthe Bonamy, Nicolas Bonichon
In 1968, Gallai conjectured that the edges of any connected graph with vertices can be partitioned into paths. We show that this conjecture is true…
A tight local algorithm for the minimum dominating set problem in outerplanar graphs
Marthe Bonamy, Linda Cook, Carla Groenland +1
We show that there is a deterministic local algorithm (constant-time distributed graph algorithm) that finds a 5-approximation of a minimum dominating set on outerplanar graphs. We…
On Vizing's edge colouring question
Marthe Bonamy, Oscar Defrain, Tereza Klimošová +2
Soon after his 1964 seminal paper on edge colouring, Vizing asked the following question: can an optimal edge colouring be reached from any given proper edge colouring through a se…