#
63 KAM Mathematical Colloquium

##
Bruce Reed

###
(McGill University, Montreal)

##
GRAPH COLOURING VIA THE PROBABILISTIC METHOD

ctvrtek 23. listopadu 2006 ve 13:00, poslucharna S5, druhe patro

KAM MFF UK

Malostranske nam. 25

118 00 Praha 1

##
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.

V pondeli 27.11.2006 v poslucharne S1 ve 12:20 prednese B. Reed navazujici druhou prednasku Graph colouring via the probabilistic
method II.

KAM MFF UK

Malostranske nam. 25

118 00 Praha 1

##
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.