|DATE:||Wednesday, November 22nd 2004.|
|TIME:||4:30 PM - 5:30 PM|
|TITLE:||Colouring Visibility Graphs|
|SPEAKER:||David Wood, School of Computer Science, McGill University|
Let P be a set of points in the plane. The visibility graph of P has vertex set P, such that two
points v and w are adjacent whenever there is no other point in P on the line segment between v and w.
The chromatic number of visibility graphs is the focus of this talk. Firstly, we characterise the 2-
and 3-chromatic visibility graphs. It is an open problem whether the chromatic number of a visibility
graph is bounded by its clique number. Our main result is a super-polynomial lower bound on the
chromatic number in terms of the clique number. This is joint work with Jan Kara and Attila Por.