Schedule

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.