Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp0147429d20b
Title: On recognition algorithms and structure of graphs with restricted induced cycles
Authors: Cook, Linda
Advisors: Seymour, Paul
Contributors: Applied and Computational Mathematics Department
Keywords: Graph Theory
Holes
Induced Subgraph
Long Even Hole
Monoholed Graph
Structural Graph Theory
Subjects: Mathematics
Computer science
Issue Date: 2021
Publisher: Princeton, NJ : Princeton University
Abstract: We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length.Forbidding holes of certain types in a graph has deep structural implications. In 2006, Chudnovksy, Seymour, Robertson, and Thomas famously proved that a graph is perfect if and only if it does not contain an odd hole or a complement of an odd hole. In 2002, Conforti, Cornuéjols, Kapoor and Vušković provided a structural description of the class of even-hole-free graphs. In Chapter 3, we provide a structural description of all graphs that contain only holes of length ℓ for every ℓ ≥ 4. Analysis of how holes interact with graph structure has yielded detection algorithms for holes of various lengths and parities.In 1991, Bienstock showed it is NP-Hard to test whether a graph G has an even (or odd) hole containing a specified vertex v∈V(G). In 2002, Conforti, Cornuéjols, Kapoor and Vušković gave a polynomial-time algorithm to recognize even-hole-free graphs using their structure theorem. In 2003, Chudnovsky, Kawarabayashi and Seymour provided a simpler and slightly faster algorithm to test whether a graph contains an even hole. In 2019, Chudnovsky, Scott, Seymour and Spirkl provided a polynomial-time algorithm to test whether a graph contains an odd hole. Later that year, Chudnovsky, Scott and Seymour strengthened this result by providing a polynomial-time algorithm to test whether a graph contains an odd hole of length at least ℓ for any fixed integer ℓ ≥ 5. In Chapter 2, we provide a polynomial-time algorithm to test whether a graph contains an even hole of length at least ℓ for any fixed integer ℓ ≥ 4.
URI: http://arks.princeton.edu/ark:/88435/dsp0147429d20b
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog: catalog.princeton.edu
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Applied and Computational Mathematics

Files in This Item:
File Description SizeFormat 
Cook_princeton_0181D_13700.pdf726.67 kBAdobe PDFView/Download


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