PIMS- UVic Discrete Math Seminar: Robert Hickingbotham

This talk will introduce the topic of graph product structure theory. I will show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the \emph{underlying treewidth} of a graph class \GG to be the minimum non-negative integer c such that, for some function f, for every graph G \in \GG there is a graph H with \tw(H) \leq c such that G is isomorphic to a subgraph of H \boxtimes K_{f(\tw(G))}. I'll introduce \emph{disjointed partitions} of graphs and show they determine the underlying treewidth of any graph class. Using this result, I will show that the class of planar graphs has underlying treewidth 3; the class of K_{s,t}-minor-free graphs has underlying treewidth s (for {t \geq \max\{s,3\}}); and the class of K_t-minor-free graphs has underlying treewidth t-2.

This is joint work with Rutger Campbell, Katie Clinch, Marc Distel, Pascal Gollin, Kevin Hendrey, Tony Huynh, Freddie Illingworth, Youri Tamitegama, Jane Tan and David Wood [https://arxiv.org/abs/2206.02395].