ORIGINAL

Abstract

Odd Cycle Transversal is the problem of finding a minimum vertex set T which intersects all odd cycles in a graph G. We study Odd Cycle Transversal with \(\mathcal{F}\)-free input graphs for various families \(\mathcal{F}\). Chiarelli et al. [4] showed that Odd Cycle Transversal is NP-Complete in H-free graphs unless H is a linear forest. The work of Courcelle et al. [10] on graphs of bounded clique-width show that Odd Cycle Transversal is solvable in polynomial time on \(P_4\)-free graphs. Dabrowski et al. [12] showed that Odd Cycle Transversal is NP-Complete in \(P_6\)-free graphs. In accordance with these results, we take particular interest in graph classes which exclude \(P_5\). We show that Odd Cycle Transversal is solvable in: (1) Subexponential time in \(P_5\)-free graphs. (2) Polynomial time in (\(P_5\), pendant)-free graphs. (3) Polynomial time in (\(P_5\), T)-free graphs for any threshold graph T. (4) Polynomial time in (\(P_5\), bull)-free graphs. The pendant is the graph comprised of an edge and a \(P_4\), where one end of the edge is complete to the \(P_4\) and the other anticomplete; threshold graphs are those which can be obtained from a single vertex by repeatedly adding vertices which are either complete or anticomplete to the existing graph; and the bull is the graph comprised of a triangle and two leaves, each with a unique neighbor in the triangle.