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.
[D] N. Dean, Open problems, Contemporary
Mathematics 147 (1993)
Submitted by: Dan Archdeacon, Dept. of Math.
Send comments to firstname.lastname@example.org