**Unavoidable apex-forest
and outerplanar graphs**

A path-decomposition of a
graph G is a finite sequence X_i of subsets of vertices such
that a) the union of the X_i is V(G), b) every edge has both endpoints in
some X_i, and c) for each vertex v, the set of X_i containing v has no gaps. The width of the path-decomposition is
the maximum value of |X_i|-1.
Large graphs of small path-width resemble ``thick paths''. The concept
is similar to that of tree-width, except here the tree is required to
be a path.

A graph G is apex-forest
if it contains a vertex v
such that G-v is a forest. A
graph is outer-planar if it
can be drawn on the plane so that every vertex is incident with the
unbounded face. Let H_1
be an apex-forest graph and H_2
be an outerplanar graph. Paul Seymour (personal communication) asks:

**Problem:** *Does every 2-connected graph
of sufficiently large path-width conatin *H_1* or *H_2* as a minor?
*

The restriction that the graph is of sufficiently large path-width
is equivalevt to requiring that it contains a sufficiently large
uniform depth binary tree as a minor.

**References:**

[D] N. Dean, Open problems, Contemporary
Mathematics 147 (1993)
677-688

Submitted by: Dan Archdeacon, Dept. of Math.
and Stat.,

Send comments to *dan.archdeacon@uvm.edu*

December 2003