-
Princeton University
-
Induced subgraphs and treewidth
Title: Induced subgraphs and treewidth
Abstract: A tree decomposition of a graph G is a way to organize G into a "tree-like" structure. A graph G has "bounded treewidth" if there is a tree decomposition of G that is "close to" a tree. Graphs with bounded treewidth have a number of nice structural and algorithmic properties. A hereditary graph class is a class of graphs defined by forbidden induced subgraphs. In this talk, we consider the following question: which hereditary graph classes have bounded treewidth? We will discuss the "central bag method," a way to prove that hereditary graph classes have bounded treewidth, and go over recent results obtained with this method.
Speaker: Tara Abrishami is a third-year PhD student in mathematics at Princeton University. Her interests are in discrete math, particularly graph theory, combinatorics, and optimization. Tara is advised by Maria Chudnovsky. Tara's current research focuses on problems in structural graph theory. She graduated from Johns Hopkins University in 2019 with bachelor’s degrees in mathematics and applied mathematics and a master’s degree in applied mathematics. She did my research and thesis on the combinatorial properties of the Laplacian eigenvalues of cographs. Outside of math, Tara enjoys writing short stories, traveling, playing board games, and making vegan food with her wonderful co-op. While she was in college, she was an artist-in-residence at Crater Lake National Park, studied abroad in Strasbourg, France, and worked as a mathematics researcher in the U.K.