
- This event has passed.
Sepehr Hajebi, Holes, hubs and bounded treewidth
Thursday, July 7, 2022 @ 10:00 AM - 11:00 AM KST
Zoom ID: 869 4632 6610 (ibsdimag)
A hole in a graph is an induced cycle of length at least four, and for every hole in , a vertex is called a -hub for if has at least neighbor in . Sintiari and Trotignon were the first to construct graphs with arbitrarily large treewidth and no induced subgraph isomorphic to the “basic obstructions,” that is, a fixed complete graph, a fixed complete bipartite graph (with parts of equal size), all subdivisions of a fixed wall and line graphs of all subdivisions of a fixed wall. They named their counterexamples “layered wheels” for a good reason: layered wheels contain wheels in abundance, where a wheel means a hole with a -hub. In accordance, one may ask whether graphs with no wheel and no induced subgraph isomorphic to the basic obstructions have bounded treewidth. This was also disproved by a recent construction due to Davies. But holes with a -hub cannot be avoided in graphs with large treewidth: graphs containing no hole with a -hub and no induced subgraph isomorphic to the basic obstructions have bounded treewidth. I will present a proof of this result, and will also give an overview of related works.
Based on joint work with Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sophie Spirkl and Kristina Vušković.