Valentin Bartier

activity

20192022

collaborators

Showing cs.DMShow all

2 papers · 1 filter

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…