Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp0144558h294
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.
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2020
Aeronautical Engineering, 1945-1975

Files in This Item:
File Description SizeFormat 
KING-JASON-THESIS.pdf445.39 kBAdobe PDF    Request a copy


Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.