Valentin Bartier

activity

20192022

collaborators

4 papers

cs.CC2022

Token sliding on graphs of girth five

Valentin Bartier, Nicolas Bousquet, Jihad Hanna +2

In the Token Sliding problem we are given a graph $G$ and two independent sets $I_{s}$ and $I_{t}$ in $G$ of size $k \geq 1$ . The goal is to decide whether there exists a sequence $\la…

cs.CC2022

Galactic Token Sliding

Valentin Bartier, Nicolas Bousquet, Amer E. Mouawad

Given a graph $G$ and two independent sets $I_{s}$ and $I_{t}$ of size $k$ , the independent set reconfiguration problem asks whether there exists a sequence of $k$ -sized independent se…

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…