10 citations · 25 across the 10 of their papers we have counts for
10 papers
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 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…
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 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…
Tree independence number I. (Even hole, diamond, pyramid)-free graphs
Tara Abrishami, Bogdan Alecu, Maria Chudnovsky +3
The tree-independence number tree-, first defined and studied by Dallard, Milanič and Štorgel, is a variant of treewidth tailored to solving the maximum independent set problem.…
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 cy…
Induced subgraphs and tree decompositions VIII. Excluding a forest in (theta, prism)-free graphs
Tara Abrishami, Bogdan Alecu, Maria Chudnovsky +2
Given a graph , we prove that every (theta, prism)-free graph of sufficiently large treewidth contains either a large clique or an induced subgraph isomorphic to , if and onl…
Induced subgraphs and tree-decompositions VII. Basic obstructions in -free graphs
Tara Abrishami, Bogdan Alecu, Maria Chudnovsky +2
We say a class of graphs is clean if for every positive integer there exists a positive integer such that every graph in with treewidth more…
Induced subgraphs and tree decompositions V. Small components of big vertices
Bogdan Alecu, Maria Chudnovsky, Kristina Vušković
Aboulker, Adler, Kim, Sintiari, and Trotignon conjectured that every graph with bounded maximum degree and large treewidth must contain, as an induced subgraph, a large subdivided…