pith. sign in

arxiv: 1609.01221 · v1 · pith:S5745L2Inew · submitted 2016-09-05 · 🧮 math.CO

Excluding a large theta graph

classification 🧮 math.CO
keywords thetagraphsfreelargegraphcharacterizationconnectedresult
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.