A characterization of K₂,4-minor-free graphs

Abstract: We provide a complete structural characterization of

K_{2, 4}

-minor-free graphs. The

3

-connected

K_{2, 4}

-minor-free graphs consist of nine small graphs on at most eight vertices, together with a family of planar graphs that contains

K_{4}

and, for each

n g e 5

,

2 n - 8

nonisomorphic graphs of order

n

. To describe the

2

-connected

K_{2, 4}

-minor-free graphs we use

x y

-outerplanar graphs, graphs embeddable in the plane with a Hamilton

x y

-path so that all other edges lie on one side of this path. We show that, subject to an appropriate connectivity condition,

x y

-outerplanar graphs are precisely the graphs that have no rooted

K_{2, 2}

-minor where

x

and

y

correspond to the two vertices on one side of the bipartition of

K_{2, 2}

. Each

2

-connected

K_{2, 4}

-minor-free graph is then (i) outerplanar, (ii) the union of three

x y

-outerplanar graphs and possibly the edge

x y

, or (iii) obtained from a

3

-connected

K_{2, 4}

-minor-free graph by replacing each edge

x_{i} y_{i}

in a set

x_{1} y_{1}, x_{2} y_{2}, l d o t s, x_{k} y_{k}

satisfying a certain condition by an

x_{i} y_{i}

-outerplanar graph.

Recommendations

Cites Work

Cited In (15)

This page was built for publication: A characterization of \(K_{2,4}\)-minor-free graphs