Graphs and Matroids - Eunjung Kim-A brief introduction to twin-width.

Abstract:Twin-width is a notion introduced in 2020 by Bonnet, Kim, Thomassé and Watrigant  which provides a unified perspective on a range of important graph classes, encompassing both sparse and dense classes. Many graph classes ranging from planar graphs, H-minor-free graphs to proper interval graphs and graphs of bounded cliquewidth have bounded twin-width. This new perspective also allows us to establish powerful properties such as tractability of First-Order model checking on many graph classes and (polynomial) χ-boundedness in a unified way. Twin-width is now considered an important part of the toolbox for structural graph theory, algorithms design, logic on finite graphs and data structure.