12 citations · 76 across the 20 of their papers we have counts for
18 papers · 1 filter
Burling graphs in graphs with large chromatic number
Tara Abrishami, Marcin Briański, James Davies +4
A graph class is -bounded if the only way to force large chromatic number in graphs from the class is by forming a large clique. In the 1970s, Erdős conjectured that intersectio…
On coarse tree decompositions and coarse balanced separators
Tara Abrishami, Jadwiga Czyżewska, Kacper Kluk +3
It is known that there is a linear dependence between the treewidth of a graph and its balanced separator number: the smallest integer such that for every weighing of the verti…
Excluding a clique or a biclique in graphs of bounded induced matching treewidth
Tara Abrishami, Marcin Briański, Jadwiga Czyżewska +4
For a tree decomposition of a graph , let denote the maximum size of an induced matching in with the property that some bag of c…
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…
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…
Induced subgraphs and tree-decompositions VII. Basic obstructions in -free graphs
Tara Abrishami, Bogdan Alecu, Maria Chudnovsky +2
We say a class of graphs is clean if for every positive integer there exists a positive integer such that every graph in with treewidth more…
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…
Induced subgraphs and tree decompositions V. One neighbor in a hole
Tara Abrishami, Bogdan Alecu, Maria Chudnovsky +3
What are the unavoidable induced subgraphs of graphs with large treewidth? It is well-known that the answer must include a complete graph, a complete bipartite graph, all subdivisi…
Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs
Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi +1
A hole in a graph is an induced cycle of length at least four, and an even hole is a hole of even length. The diamond is the graph obtained from the complete graph by rem…
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…
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…