School Seminars and Colloquia

Problems in Geometric Graph Theory

Confirmation talk

by Michael Payne


Institution: Dept of Mathematics & Statistics, The University of Melbourne
Date: Tue 25th January 2011
Time: 3:00 PM
Location: Room 215, Richard Berry Building, The University of Melbourne

Abstract: Geometric Graph Theory deals with classes of graphs that arise from various geometric settings. During my first year of candidature I have
addressed problems involving two such classes. The first is that of colouring great circle arrangement graphs. These graphs have the
crossing points of a set of great circles as vertices and the arcs as edges. Since they are planar graphs they are 4-colourable, but it is
conjectured that three colours suffice. The second problem involves the visibility graphs of point sets in the plane. Two points in the set are joined by an edge if no other point lies on the straight line
segment between them. I have investigated the question of whether visibility graphs with a fixed clique number (c) have bounded chromatic number. The answer is known to be yes for c=3 and no for
c=6. I have studied the first remaining case, c=4.

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