Valentin Bartier

activity

20192024

most citedOn girth and the parameterized complexity of token sliding and token jumping

14 citations · 14 across the 4 of their papers we have counts for

collaborators

Showing cs.DMShow all

3 papers · 1 filter

cs.DM2024

Independent set reconfiguration in H-free graphs

Valentin Bartier, Nicolas Bousquet, Moritz Mühlenthaler

Given a graph $G$ and two independent sets of $G$ , the independent set reconfiguration problem asks whether one independent set can be transformed into the other by moving a single…

cs.DM2020

Recoloring graphs of treewidth 2

Valentin Bartier, Nicolas Bousquet, Marc Heinrich

Two (proper) colorings of a graph are adjacent if they differ on exactly one vertex. Jerrum proved that any $(d + 2)$ -coloring of any d-degenerate graph can be transformed into any…

cs.DM2019

Linear transformations between colorings in chordal graphs

Nicolas Bousquet, Valentin Bartier

Let $k$ and $d$ be such that $k \geq d + 2$ . Consider two $k$ -colorings of a $d$ -degenerate graph $G$ . Can we transform one into the other by recoloring one vertex at each step while…