Unavoidable Induced Subgraphs of Large Graphs

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.