Twin-Width of Graphs

Twin-width is a graph complexity measure based on a notion of width of permutations by Guillemot and Marx [SODA '14]. Twin-width is defined through sequences of d-contractions, which witness that the twin-width is at most d. Notable classes of graphs with bounded twin-width are proper minor-closed graphs, and classes width bounded clique-width. FO model checking is FPT with regards to twin-width, provided that a good contraction sequence is given in the input. This seminar is meant as an introduction to twin-width, going over the basic definitions and results (stability results, characterization through matrices), and presenting the main theorems.