Skip navigation
Please use this identifier to cite or link to this item:
Title: The central bag method: An approach to analyzing the structure of hereditary graph classes
Authors: Abrishami, Tara
Advisors: Chudnovsky, Maria
Contributors: Applied and Computational Mathematics Department
Keywords: graph theory
maximum weight independent set
tree decomposition
Subjects: Mathematics
Issue Date: 2023
Publisher: Princeton, NJ : Princeton University
Abstract: In this thesis we develop the central bag method. The central bag method uses the structure of cutsets in a graph G to construct an induced subgraph B of G with two key features: 1. Every component of G - B has small weight and has constant-size neighborhood in B; and 2. the properties of B are "nicer'" than the properties of G. The central bag was inspired by properties of tree decompositions and is analogous to a single bag of a well-chosen tree decomposition of G. The main application of the central bag method is to prove that hereditary graph classes have bounded treewidth. In this thesis, we show how the central bag method can be used to prove that (theta, pyramid, prism, line wheel, Kt)-free graphs have logarithmic treewidth (in the number of vertices), that (even hole, pyramid, diamond, Kt)-free graphs have constant treewidth, and that (propeller, Wtxt, Kt)-free graphs have constant treewidth. The central bag method has also been used to prove that the Maximum Weight Independent Set problem (MWIS) is polynomial-time solvable in certain hereditary graph classes. In this thesis, we show how the central bag method can be used to prove that MWIS is polynomial-time solvable in a subclass of perfect graphs and in (Sttt, Kt, Ktt)-free graphs.
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Applied and Computational Mathematics

Files in This Item:
File Description SizeFormat 
Abrishami_princeton_0181D_14703.pdf668.93 kBAdobe PDFView/Download

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