33 citations · 242 across the 67 of their papers we have counts for
20 papers · 1 filter
Digraph redicolouring
Nicolas Bousquet, Frédéric Havet, Nicolas Nisse +2
Given two -dicolourings of a digraph , we prove that it is PSPACE-complete to decide whether we can transform one into the other by recolouring one vertex at each step while…
The smallest 5-chromatic tournament
Thomas Bellitto, Nicolas Bousquet, Adam Kabela +1
A coloring of a digraph is a partition of its vertex set such that each class induces a digraph with no directed cycles. A digraph is -chromatic if is the minimum number of…
Short and local transformations between ()-colorings
Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich +1
Recoloring a graph is about finding a sequence of proper colorings of this graph from an initial coloring to a target coloring . Adding the constraint that each pair of cons…
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 -coloring of any d-degenerate graph can be transformed into any…
Linear transformations between dominating sets in the TAR-model
Nicolas Bousquet, Alice Joffard, Paul Ouvrard
Given a graph and an integer , a token addition and removal ({\sf TAR} for short) reconfiguration sequence between two dominating sets and of size at…
Linear transformations between colorings in chordal graphs
Nicolas Bousquet, Valentin Bartier
Let and be such that . Consider two -colorings of a -degenerate graph . Can we transform one into the other by recoloring one vertex at each step while…