Every graph is essential to large treewidth

-
Nicolas Trotignon , ENS Lyon
Fine Hall 224

We show that for every graph H, there is a hereditary class of graphs C with unbounded treewidth such that the graphs in C that do not contain H as an induced subgraph have bounded treewidth. This refutes several conjectures and puts some limit to the quest for the unavoidable induced subgraphs in classes of unbounded treewidth. Our construction is a variant of so-called layered wheels. This is joint work with Bogdan Alecu, Édouard Bonnet and Pedro Bureo Villafana.