Excluding a large theta graph

Abstract: A theta graph, denoted

h e t a_{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

h e t a_{a, b, c}

as a topological minor. More specifically, we describe the structure of

h e t a_{1, 2, t}

-,

h e t a_{2, 2, t}

-,

h e t a_{1, t, t}

-,

h e t a_{2, t, t}

-, and

h e t a_{t, t, t}

-free graphs where

t

is large. The main result is a characterization of

h e t a_{t, t, t}

-free graphs for large

t

. The

3

-connected

h e t a_{t, t, t}

-free graphs are formed by

3

-summing graphs without a long path to certain planar graphs. The

2

-connected

h e t a_{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.

Recommendations

Cites work

Cited in

(1)

Minors in graphs of large \(\theta_r\)-girth

This page was built for publication: Excluding a large theta graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q723880)