School Seminars and Colloquia

Colouring Circular Arc Graphs

Confirmation talk

by Daniel Harvey


Institution: Department of Mathematics and Statistics
Date: Fri 4th February 2011
Time: 11:00 AM
Location: Room 215, Richard Berry Building, The University of Melbourne

Abstract: Circular arc graphs are a class of graphs that can be represented by a
set of arcs on a circle. Colouring problems on circular arc graphs can
be used to model job allocation and certain problems in optical ring networks.
Our goal is to solve a series of colouring problems for the class of circular
arc graphs, including the Double Critical Graph Conjecture, the more general
Erdos-Lovasz Tihany Conjecture, and Hadwiger's conjecture. We choose to
consider this class of graphs as they are chi-bounded without being perfect.
Thus the above graph colouring problems are interesting, nontrivial, and achievable.

For More Information: contact: David Wood. email: woodd@unimelb.edu.au