SPECIAL
YEAR ON GRAPH THEORY AND COMBINATORIAL OPTIMIZATION
Workshop on Graph Minors and Topological Graph Theory
January 17- 22, 2000
Organizer: Bruce Richter Technical University of Waterloo
Invited Lecturer: Carsten Thomassen Mathematical Institute,
University of Denmark
Title: Colourings and Topological Graph Theory
Abstract:
Developments in Topological Graph Theory over the last few years will
be surveyed, from basic topological results such as the Jordan Curve
Theorem, to very current work. Particular attention will be devoted
to recent work in the colouring of graphs embedded in surfaces. Open
questions will be highlighted.
The invited lecturer will introduce background and recent results,
together with some open problems. The remaining time will be devoted
to informal sessions which will provide a forum for discussions and
an exchange of ideas on a broad spectrum of problems .
In the context of graph minors, a very basic problem is to classify
all graphs that do not have the complete graph on n vertices as a minor.
We do not yet have a characterization even for the case n=6. This is
related to Hadwiger's Conjecture, which says that a graph without Kn
as a minor is n-1 colourable. This generalization of the 4-Colour Theorem
has only been proved for n=5 (= the 4-Colour Theorem) and n=6.
In the context of topological graph theory, the interaction between
graph theory and the topology of curves in surfaces continues to provide
many interesting questions. From the work of Robertson and Seymour,
the concept of representativity of an embedding in a surface became
prominent. This is the least number of times a noncontractible curve
in the surface intersects the embedded graph. Zha has conjectured that
if the genus of the surface is at least 2 and the representativity of
the embedding is at least 3, then there is a cycle in the embedded graph
that is noncontractible in the surface and separates the surface. The
best result to date requires representativity at least 6. A purely combinatorial
question about the topology of a surface that comes up from the study
of minor minimal k-representative embeddings is: What is the maximum
number pairwise nonhomotopic noncontractible cycles in a fixed surface
so that pairwise the curves have at most t intersections? It has been
shown that this number, which depends on the surface and on t, is finite.
For t=0 ,exact results are known, but it is not even clear what the
order of magnitude is for t=1.
