12 citations · 27 across the 6 of their papers we have counts for
6 papers · 1 filter
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 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…
Submodular functions and perfect graphs
Tara Abrishami, Maria Chudnovsky, Cemil Dibek +1
We give a combinatorial polynomial-time algorithm to find a maximum weight independent set in perfect graphs of bounded degree that do not contain a prism or a hole of length four…
Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree
Tara Abrishami, Maria Chudnovsky, Cemil Dibek +4
This paper is motivated by the following question: what are the unavoidable induced subgraphs of graphs with large treewidth? Aboulker et al. made a conjecture which answers this q…
Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree
Tara Abrishami, Maria Chudnovsky, Kristina Vušković
Treewidth is a parameter that emerged from the study of minor closed classes of graphs (i.e. classes closed under vertex and edge deletion, and edge contraction). It in some sense…
Graphs with polynomially many minimal separators
Tara Abrishami, Maria Chudnovsky, Cemil Dibek +3
We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the…