A gentle introduction to twin-width

10^th January 2023, 13:00 6th Floor Conference Room 605, EEE
Dr. Édouard Bonnet
University of Lyon, CNRS, ENS de Lyon

Abstract

We define the new graph parameter, twin-width, and survey some algorithmic applications and structural properties of graph classes with bounded twin-width. We will also see that contraction sequences --which are used to define twin-width-- yield some characterizations of preexisting width parameters, such as cliquewidth. Unlike the abstract, the talk will assume no specific knowledge in graph theory.

The talk is based on joint works with Colin Geniet, Eunjung Kim, Amadeus Reinald, Stéphan Thomassé, and Rémi Watrigant.