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.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at beezer at cs.mcgill.ca.

www.cs.mcgill.ca/~beezer/Seminars/