Induced subgraphs and tree decompositions XIV. Non-adjacent neighbours in a hole
arXiv:2311.05719 · doi:10.1016/j.ejc.2024.104074
Abstract
A clock is a graph consisting of an induced cycle and a vertex not in with at least two non-adjacent neighbours in . We show that every clock-free graph of large treewidth contains a "basic obstruction" of large treewidth as an induced subgraph: a complete graph, a subdivision of a wall, or the line graph of a subdivision of a wall.