Description

The research area of graph colouring has a rich history involving a combination of important theorems and long-standing open conjectures. In addition to the pure and theoretical aspects of graph colouring, there are several natural applications, most especially within the realm of scheduling. Moreover, the study of graph colouring provides a good opportunity to introduce students to proof techniques involving fractional graph theory and the probabilistic method.

Tentatively this graduate course will cover the following topics:

• Edge colourings: types of edge colourings (proper, equalised, equitable, balanced), Vizing’s theorem, overfull graphs, Fournier’s theorem, the Chetwynd-Hilton-Hoffman theorem, critical graphs.
• Vertex colourings: bounds on the chromatic number, Brooks’ theorem, Hadwiger’s conjecture, Reed’s conjecture, colour-critical graphs, Turan’s theorem, the Erdös-Faber-Lovász conjecture.
• Total colourings: the total colouring conjecture, total colourings of complete and complete multipartite graphs, classification of type 1 and type 2 graphs, total colourings of planar graphs.
• Fractional colourings: bounds on the fractional chromatic number, proof of the Erdös-Faber-Lovász conjecture, proof of Reed’s conjecture, fractional edge colouring, fractional total colouring.

Prerequisites

Math-6340 or permision from the instructor.

References

• G. Chartrand and P. Zhang. Chromatic graph theory. CRC Press, 2009.
• R. Diestel. Graph theory, third edition. Springer, 2005.
• T.R. Jensen and B. Toft. Graph coloring problems. Wiley, 1994.
• M. Molloy and B. Reed. Graph colouring and the probabilistic method. Springer, 2002.
• E.R. Scheinermann and D.H. Ullman. Fractional graph theory. Wiley, 1997.
• H.P. Yap. Total colourings of graphs. Springer, 1996.