63 KAM Mathematical Colloquium

Bruce Reed

(McGill University, Montreal)

GRAPH COLOURING VIA THE PROBABILISTIC METHOD

Abstract

The Four Colour Theorem (that any map can be coloured with four colours so that countries which share a boundary receive different colours) is probably the most famous graph theory result. We reformulate this result as a statement about graphs by considering the graph which has a vertex for each country and in which two vertices are joined by an edge precisely if the corresponding countries share a boundary. In this formulation, the 4CT states that a graph which can be drawn in the plane so that edges meet only at their common endpoints can be coloured with four colours so that there are no monochromatic edges.

We will be interested in determining the minimum number of colours required to colour an arbitrary graph. In general, this is a difficult question which depends on the global structure of the graph. However, for certain classes of graphs it has been shown that this number can be determined (either exactly or approximately) by considering the local structure of the graph. There are other classes where this is believed to be the case but has not been proved.

We discuss some results and open problems with this flavor. Many of these results are proved using the probabilistic method. The presentation will be accessible and non-technical, further details for experts will be given at a seminar.

Abstract

I will discuss more examples of optimal or near optimal graph colourings obtained via the probabilistic method. This talk will go into more detail than the colloquium talk.
 

O přednášejícím

Prof. Reed studoval na McGill University (jeho skolitelem byl V. Chvatal) a posleze byl pracovnikem prednich instituci v USA, Kanade, Nemecku a Francii. V soucasnosti je profesorem na McGill University a je rovnez Direceour de Recherche II, CNRS, Paris. Byl a je aktivne cinny ve vetsine oblasti moderni kombinatoriky a teorie grafu, pravdepodobnostnich modelu a teoreticke informatiky. Prof. Reed je mezinarodne znamym matematikem, editorem nekolika casopisu. Na Mezinarodnim kongresu matematiku v Pekingu v roce 2002 prednesl zvanou prednasku. Je autorem 3 knih, vcetne zname Graph Theory and the Probabilistic Method (Springer 2001). Z teto oblasti je rovnez jeho prazske kolokvium.