12 citations · 76 across the 20 of their papers we have counts for
7 papers · 1 filter
Graphs with no even holes and no sector wheels are the union of two chordal graphs
Tara Abrishami, Eli Berger, Maria Chudnovsky +1
Sivaraman conjectured that if is a graph with no induced even cycle then there exist sets satisfying such that the induced graph…
Max Weight Independent Set in sparse graphs with no long claws
Tara Abrishami, Maria Chudnovsky, Cemil Dibek +2
We revisit the recent polynomial-time algorithm for the MAX WEIGHT INDEPENDENT SET (MWIS) problem in bounded-degree graphs that do not contain a fixed graph whose every component i…
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…
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…
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…