| DATE: | Wednesday, November 22nd 2004. |
| TIME: | 4:30 PM - 5:30 PM |
| PLACE: | McConnell 320 |
| 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.