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…