Premium
Erdős–Pósa property of obstructions to interval graphs
Author(s) -
Agrawal Akanksha,
Lokshtanov Daniel,
Misra Pranabendu,
Saurabh Saket,
Zehavi Meirav
Publication year - 2023
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22895
Subject(s) - combinatorics , mathematics , disjoint sets , cograph , vertex (graph theory) , discrete mathematics , chordal graph , split graph , interval graph , graph , indifference graph , property (philosophy) , maximal independent set , 1 planar graph , philosophy , epistemology
A class of graphsℱ ${\rm{ {\mathcal F} }}$ admits the Erdős–Pósa property if for any graphG $G$ , eitherG $G$ hask $k$ vertex‐disjoint “copies” of the graphs inℱ ${\rm{ {\mathcal F} }}$ , or there is a setS ⊆ V ( G )$S\subseteq V(G)$ off ( k )$f(k)$ vertices that intersects all copies of the graphs inℱ ${\rm{ {\mathcal F} }}$ . For any graph classG ${\mathscr{G}}$ , it is natural to ask whether the family of obstructions toG ${\mathscr{G}}$ 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 graphG $G$ hask $k$ vertex‐disjoint AWs and chordless cycles, or there exists a set ofO ( k 2 log k )${\mathscr{O}}({k}^{2}\mathrm{log}k)$ vertices inG $G$ that hits all AWs and chordless cycles.