6 papers · 1 filter
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…
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 VI. Graphs with 2-cutsets
Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi +1
This paper continues a series of papers investigating the following question: which hereditary graph classes have bounded treewidth? We call a graph -clean if it does not contai…
Excluding the fork and antifork
Maria Chudnovsky, Linda Cook, Paul Seymour
The fork is the tree obtained from the claw by subdividing one of its edges once, and the antifork is its complement graph. We give a complete description of all graphs t…
Even pairs in Berge graphs with no balanced skew-partitions
Tara Abrishami, Maria Chudnovsky, Yaqian Tang
Let be a Berge graph that has no odd prism and no antihole of length at least six as an induced subgraph. We show that every such graph with no balanced skew-partition is e…