Graph Minors (08w5079)

Objectives

A monumental project in graph theory by Robertson and Seymour was recently completed. This is now called "Graph Minor Theory", and
Graph Minors project resulted in many theoretical advances, (e.g. a proof of Wagner's conjecture), but it also has algorithmic applications, and some of the methods have been successfully used in practical computation.

But currently, Graph Minor theory is reasonably understood by many, and several researchers have been working on extensions of Graph minor project. A research program conducted by Jim Geelen, Bert Gerards and
Geoff Whittle are extending the results and techniques of the Graph Minor Project of Robertson and Seymour to matroids. They have already published over 10 papers in Journal of Combinatorial Theory Ser. B (All Graph minor theory papers, except for "Graph Minors II", appeared in Journal of Combinatorial Theory Ser. B.). So this project is really "tour de force".

Also, techniques and tools from Graph Minor Theory are reasonably understood by many, and some researchers have been working on exact structural descriptions using them. Let us observe that the decomposition theorem capturing the structure of all graphs excluding a fixed minor is, in a sense, an approximate structure theorem since this structure could contain the minor which we would like to exclude. A proof of Jorgensen's conjecture for large graphs by Robin Thomas and his team may give new insight in this direction since an apex graph, i.e., it has a vertex $v$ such that $G-v$ is planar, clearly does not contain $K_6$-minors.

As we see the above two examples, there are now research programs which are a far reaching generalizations of Graph Minor Theory and are deep understandings of techniques and tools from Graph Minor Theory. So we feel that it is now time to gather many researchers who are working on
Graph Minor area, and present "state of art" of their current projects.
In particular, it seems important to report where these projects stand and where these projects would go.

In particular, we shall focus on the following two points: extensions of Graph Minor Theory, and applications of Graph Minor Theory techniques and tools.