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

Cook_princeton_0181D_13700.pdf | 726.67 kB | Adobe PDF | View/Download |

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