Graph Minors (08w5079)


(National Institute of Informatics)

Bojan Mohar (Simon Fraser University)

(McGill University)

Paul Seymour (Princeton University)


The Banff International Research Station will host top researchers in its workshop on "Graph Minors" next week, September 28 - October 3, 2008. A monumental project in graph theory was recently completed by Robertson and Seymour. This is now called "Graph Minor Theory". The
Graph Minors project has 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.

Currently, Graph Minor Theory is reasonably understood by many,
and several researchers have been working on extensions of the Graph Minor
project. Also, techniques and tools from Graph Minor Theory are reasonably
understood, and some research groups have been working on
exact structural descriptions using them.
It is now time to gather various research groups who are working on
Graph Minors and present a "state of art" of their current projects.
It seems important to report where these projects stand
and where they would go. In particular,
we shall focus on the following two areas: extensions of
Graph Minor Theory and applications of Graph Minor Theory techniques
and tools.

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the US National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnologí­a (CONACYT).