Even-hole free graphs of bounded degree have bounded treewidth

Abstract: Tree decompositions are a powerful tool in structural graph theory that is traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has so far largely remained out of reach. Traditionally to bound the treewidth of a graph, one finds a way to decompose it by a so-called laminar collection of decompositions. Recently, in joint work with Tara Abrishami and Kristina Vuskovic, we proved that even-hole free graphs of bounded degree have bounded tree-width. To do so we used "star cutset separations" that arise naturally in the context of even-hole-free graphs. While the set of star cutset separations is far from being non-crossing, it turns out that one can partition it into a bounded number of laminar collections, and this is sufficient for our purposes. In this talk we will present an outline of the proof.

combinatorics

Audience: researchers in the topic

Warwick Combinatorics Seminar

Series comments: This is the online combinatorics seminar at Warwick.