Skip navigation
Please use this identifier to cite or link to this item:
Title: Unavoidable Induced Subgraphs of Large Graphs
Authors: Pohoata, Andrei Cosmin
Advisors: Seymour, Paul
Contributors: van Zwam, Stefan
Department: Mathematics
Class Year: 2014
Abstract: A theorem of Galvin, Rival and Sands [5] states that every graph with a large path contains either a large induced path or a large complete bipartite subgraph (not necessarily induced). By a standard Ramsey theory argument, this is equivalent to saying that every graph with a large path subgraph contains either a large path, a large clique, or a large complete bipartite graph as an induced subgraph. This is sharp in the sense that any induced subgraph ideal with arbitrary large path subgraphs includes one of the minimal induced subgraph ideals containing all paths, cliques, or complete bipartite graphs. We appropriately call these graphs the unavoidable induced subgraphs with respect to large path subgraph containment. In this thesis, we prove similar theorems for graphs containing other large structures. In particular, we find the unavoidable induced subgraphs of graphs that contain large cycles, stars or binary trees as subgraphs, topological minors, or simply as minors. Along the way, we also find a qualitative obstruction to graphs of bounded treewidth having large pathwidth.
Extent: 45 pages
Type of Material: Princeton University Senior Theses
Language: en_US
Appears in Collections:Mathematics, 1934-2020

Files in This Item:
File SizeFormat 
Andrei Cosmin Pohoata thesis.pdf858.53 kBAdobe PDF    Request a copy

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