Excluding a large theta graph

Abstract

A theta graph, denoted ${\theta }_{a,b,c}$, is a graph of order $a+b+c-1$ consisting of a pair of vertices and three independent paths between them of lengths $a$, $b$, and $c$. We provide a complete characterization of graphs that do not contain a large ${\theta }_{a,b,c}$ as a topological minor. More specifically, we describe the structure of ${\theta }_{1,2,t}$-, ${\theta }_{2,2,t}$-, ${\theta }_{1,t,t}$-, ${\theta }_{2,t,t}$-, and ${\theta }_{t,t,t}$-free graphs where $t$ is large. The main result is a characterization of ${\theta }_{t,t,t}$-free graphs for large $t$. The $3$-connected ${\theta }_{t,t,t}$-free graphs are formed by $3$-summing graphs without a long path to certain planar graphs. The $2$-connected ${\theta }_{t,t,t}$-free graphs are then built up in a similar fashion by 2- and 3-sums. This result implies a well-known theorem of Robertson and Chakravarti on graphs that do not have a bond containing three specified edges.

27 pages, 8 figures