Even-hole-free graphs with bounded degree have bounded treewidth

Speaker: Tara Abrishami (Princeton)

Abstract: We prove that even-hole-free graphs with bounded degree have bounded treewidth, resolving a conjecture of Aboulker, Adler, Kim, Sintiari, and Trotignon. To do this, we show that if G is an even-hole-free graph with bounded degree, then G can be iteratively decomposed by collections of separations given by star cutsets and double star cutsets of G. This results in an induced subgraph β of G such that β has no star cutset, and β has bounded treewidth only if G has bounded treewidth. We show that even-hole-free graphs with bounded degree and no star cutset have bounded treewidth, completing the proof.

This is joint work with Maria Chudnovsky and Kristina Vuskovic.

Date and time: 17/09/2020 at 15:00 (UTC+2)

Link to the talk: https://bbb-temp.grenet.fr/b/lou-9x7-69p