6 papers
Induced subgraphs and tree decompositions XI. Local structure in even-hole-free graphs of large treewidth
Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi +1
We prove a conjecture of Sintiari and Trotignon that every even-hole-free graph of sufficiently large treewidth contains a four-vertex induced subgraph with at least five edges (th…
Induced subgraphs and tree decompositions X. Towards logarithmic treewidth for even-hole-free graphs
Tara Abrishami, Bogdan Alecu, Maria Chudnovsky +2
A generalized -pyramid is a graph obtained from a certain kind of tree (a subdivided star or a subdivided cubic caterpillar) and the line graph of a subdivided cubic caterpillar…
Every Graph is Essential to Large Treewidth
Bogdan Alecu, Ãdouard Bonnet, Pedro Bureo Villafana +1
We show that for every graph , there is a hereditary weakly sparse graph class of unbounded treewidth such that the -free (i.e., excluding as an induced su…
Induced subgraphs and tree decompositions IX. Grid theorem for perforated graphs
Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi +1
The celebrated ErdÅs-Pósa Theorem, in one formulation, asserts that for every , graphs with no subgraph (or equivalently, minor) isomorphic to the disjoint union of …
Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs
Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi +1
Given an integer , we say a graph is -pinched if does not contain an induced subgraph consisting of cycles, all going through a single common vertex…
Induced subgraphs and tree decompositions XIII. Basic obstructions in -free graphs for finite
Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi +1
Unlike minors, the induced subgraph obstructions to bounded treewidth come in a large variety, including, for every , the -basic obstructions: the graphs and…