Treewidth via spined categories
Zoltan Kocsis – 23 June 2021
Treewidth is a well-known graph invariant with multiple interesting applications in combinatorics. On the theoretical side, treewidth played an essential role in the proof of the Robertson-Seymour graph minor theorem. On the practical side, many NP-complete problems are polynomial-time (sometimes even linear-time) solvable on graphs of bounded treewidth. The aim of this talk is to introduce our recent work (w/ Ben Bumpus, University of Glasgow; arXiv:2105.05372) on spined categories: categories equipped with extra structure that permits the definition of a functorial analogue of treewidth. I'll explain the construction, and show that the usual notions of treewidth and hypergraph treewidth are recovered as its special cases. Time permitting, I will touch upon some open questions and computational aspects as well.
Back