Twin-Width of Graphs

Speaker(s)

Colin Geniet

Affiliation

ENS Paris-Saclay

Date

Oct. 14, 2020, 2 p.m.

Information about the event

online

Seminar

Seminar Automata Theory

---

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.

---