12 citations · 76 across the 20 of their papers we have counts for
4 papers · 1 filter
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…
Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws
Tara Abrishami, Maria Chudnovsky, Cemil Dibek +1
For graphs and , we say that is -free if it does not contain as an induced subgraph. Already in the early 1980s Alekseev observed that if is connected, then t…