Colouring Circular Arc Graphs
by Daniel Harvey
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: firstname.lastname@example.org