29 citations · 334 across the 88 of their papers we have counts for
7 papers · 1 filter
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…
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…
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…
Complexity of -coloring in hereditary classes of graphs
Maria Chudnovsky, Shenwei Huang, Paweł Rzążewski +2
For a graph , a graph is \emph{-free} if it does not contain an induced subgraph isomorphic to . For two graphs and , an \emph{-coloring} of is a mapping…
Finding large -colorable subgraphs in hereditary graph classes
Maria Chudnovsky, Jason King, Michał Pilipczuk +2
We study the \textsc{Max Partial -Coloring} problem: given a graph , find the largest induced subgraph of that admits a homomorphism into , where is a fixed patter…
Induced subgraphs of bounded treewidth and the container method
Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk +2
A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By we denote a path on vertices. In this paper we give polynomial-…