Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01k0698b538
 Title: Odd Cycle Transversal in Hereditary Graph Classes Authors: King, Jason Advisors: Chudnovsky, Maria Department: Mathematics Class Year: 2020 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. URI: http://arks.princeton.edu/ark:/88435/dsp01k0698b538 Type of Material: Princeton University Senior Theses Language: en Appears in Collections: Mathematics, 1934-2020