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 | Size | Format | |
---|---|---|---|---|

KING-JASON-THESIS.pdf | 445.39 kB | Adobe PDF | Request a copy |

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