Induced subgraphs and tree decompositions XIV. Non-adjacent neighbours in a hole

Abstract

A clock is a graph consisting of an induced cycle $C$ and a vertex not in $C$ with at least two non-adjacent neighbours in $C$. 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.

References in corpus (4)

• Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree
• Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs
• Induced subgraphs and tree decompositions V. One neighbor in a hole
• Submodular functions and perfect graphs