Lansdowne Lecture - Ringel's Decomposition Problem and Graph Labellings

Wednesday March 29th at 7 PM until 8 PM

University of Victoria  (David Strong Building, C103)

Free and open to everyone

Event Website

Speaker: Professor Alexander Rosa (Emeritus Professor, Department of Mathematics and Statistics, McMaster University)


During the 1963 international graph theory conference in Smolenice, Czechoslovakia, Gerhard Ringel formulated the following conjecture:

The complete graph with vertices can be decomposed into subgraphs, each isomorphic to a given tree with edges.

Shortly thereafter, several kinds of graph labellings were introduced with the aim of attacking Ringel’s conjecture. Among these, the graceful labelling (originally called labelling) became the most prominent.

I will attempt to present an overview of the up-to-date approaches to Ringel’s conjecture, and also to the well-known conjecture that every tree has a graceful labelling.

View Larger Map