Nicolas Bousquet: Fast transformations between colorings

Description of video

Date: 3/11/22
Speaker :Bousquet Nicolas

Given a graph G=(V,E), a k-coloring is an assignment of colors in {1,...,k} to vertices such that adjacent vertices receive distinct colors. Proving the existence of k-colorings received a considerable in the last decades. In this talk, we will focus on the existence of transformations between colorings rather than finding coloring themselves. A transformation between two colorings c_1,c_2 is a sequence of proper colorings starting in c_1 and ending in c_2 such that consecutive colorings differ on exactly one vertex. We will first motivate this problem by explaining its relation with enumeration and random generation. We will then overview some recent results of the field together with intuitions of their proofs