Please note: This PhD seminar will take place in MC 5479.
Taite LaGrange, PhD candidate
David R. Cheriton School of Computer Science
Supervisors: Professors Therese Biedl, Sophie Spirkl
Twin-width is a graph and matrix parameter introduced in 2021 by Bonnet, Kim, Thomassé, and Watrigant as essentially a measure of the ‘error’ between vertex neighbourhoods over a series of vertex contractions.
This talk covers some graph classes with unbounded twin-width. We present a tool for obtaining twin-width bounds in general by contracting a graph based on a partition by distinct neighbourhoods. For a graph G on n vertices, we show that if such a partition exists, then the twin-width of G is at worst sub-linear with respect to n. We use this to obtain an upper bound on the twin-width of interval graphs and of graphs with bounded VC dimension. The latter implies that hereditary classes have sub-linear twin-width if and only if they have bounded VC dimension.