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., University of Vermont, Burlington, VT 05401-1455 USA

Send comments to dan.archdeacon@uvm.edu

December 2003