Prof. Meirav Zehavi

A class of graphs (Formula presented.) admits the Erdős–Pósa property if for any graph (Formula presented.), either (Formula presented.) has (Formula presented.) vertex-disjoint “copies” of the graphs in (Formula presented.), or there is a set (Formula presented.) of (Formula presented.) vertices that intersects all copies of the graphs in (Formula presented.). For any graph class (Formula presented.), it is natural to ask whether the family of obstructions to (Formula presented.) has the Erdős–Pósa property. In this paper, we prove that the family of obstructions to interval graphs—namely, the family of chordless cycles and asteroidal witnesses (AWs)—admits the Erdős–Pósa property. In turn, this yields an algorithm to decide whether a given graph (Formula presented.) has (Formula presented.) vertex-disjoint AWs and chordless cycles, or there exists a set of (Formula presented.) vertices in (Formula presented.) that hits all AWs and chordless cycles.