23 citations · 150 across the 51 of their papers we have counts for
4 papers · 1 filter
Gallai's path decomposition conjecture for graphs of small maximum degree
Marthe Bonamy, Thomas Perrett
Gallai's path decomposition conjecture states that the edges of any connected graph on n vertices can be decomposed into at most (n+1)/2 paths. We confirm that conjecture for all g…
Tight lower bounds for the complexity of multicoloring
Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk +2
In the multicoloring problem, also known as (:)-coloring or -fold coloring, we are given a graph G and a set of colors, and the task is to assign a subset of color…
Token Sliding on Chordal Graphs
Marthe Bonamy, Nicolas Bousquet
Let I be an independent set of a graph G. Imagine that a token is located on any vertex of I. We can now move the tokens of I along the edges of the graph as long as the set of tok…
On the difference between the Szeged and Wiener index
Marthe Bonamy, Martin Knor, Borut Lužar +2
We prove a conjecture of Nadjafi-Arani, Khodashenas and Ashrafi on the difference between the Szeged and Wiener index of a graph. Namely, if is a 2-connected non-complete graph…