29 citations · 334 across the 88 of their papers we have counts for
111 papers
Excluding the fork and antifork
Maria Chudnovsky, Linda Cook, Paul Seymour
The fork is the tree obtained from the claw by subdividing one of its edges once, and the antifork is its complement graph. We give a complete description of all graphs t…
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 XII. Grid theorem for pinched graphs
Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi +1
Given an integer , we say a graph is -pinched if does not contain an induced subgraph consisting of cycles, all going through a single common vertex…
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…
Sparse induced subgraphs in P_6-free graphs
Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk +2
We prove that a number of computational problems that ask for the largest sparse induced subgraph satisfying some property definable in CMSO2 logic, most notably Feedback Vertex Se…
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.…