Tag: SepehrHajebi

A hole in a graph $G$ is an induced cycle of length at least four, and for every hole $H$ in $G$, a vertex $h\in G\setminus H$ is called a $t$-hub for $H$ if $h$ has at least $t$ neighbor in $H$. 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 $3$-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 $2$-hub cannot be avoided in graphs with large treewidth: graphs containing no hole with a $2$-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ć.