Containment Relations and Line Graphs

Abstract

This dissertation studies several problems involving containment relations and line graphs. First, motivated by Reed and Seymour's 2004 result that Hadwiger's Conjecture holds for line graphs, we provide a partial result towards the immersion-analog of their theorem. Namely, we show that Abu-Khzam and Langston's Conjecture on clique immersions in graphs with high chromatic number holds for line graphs of multigraphs with constant edge multiplicity. We also examine the relationship between clique minors and clique immersions in line graphs, showing that when $G$ is a line graph, $G$ has a $K_t$-immersion iff $G$ has a $K_t$-minor whenever $t\leq 4$, but this equivalence fails in both directions when $t=5$. These results have already appeared in the journal \textit{Discrete Mathematics}.

The second topic in this thesis takes a broader look at some interactions concerning line graphs and containment relations when the target graph need not be a clique. We first prove that if one graph $H_1$ contains another graph $H_2$ as an immersion (or topological minor), then $L(H_1)$ contains $L(H_2)$ as a minor. We also get a result exploring the backwards direction of this statement. Focusing on the topological minor relation, we show that if a simple graph is not a line graph then there is no sequence of subdivisions that can be done to obtain a line graph from it.

As a final topic in this dissertation we introduce the notion of $k$-restricted immersions, intended to bridge the gap between the notions of immersions and topological minors. We make several fundamental observations and provide a sufficient condition for when 2-restricted immersions and topological minors are equivalent. We also put forth several conjectures related to this new idea of restriction and detail some of our current progress.