12 citations · 76 across the 20 of their papers we have counts for
3 papers · 2 filters
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 III. Three-path-configurations and logarithmic treewidth
Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi +1
A theta is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family of graphs, we s…
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…