Erdős–Pósa property of obstructions to interval graphs

AbstractA class of graphs admits the Erdős–Pósa property if for any graph , either has vertex‐disjoint “copies” of the graphs in , or there is a set of vertices that intersects all copies of the graphs in . For any graph class , it is natural to ask whether the family of obstructions to 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 has vertex‐disjoint AWs and chordless cycles, or there exists a set of vertices in that hits all AWs and chordless cycles.