Advance techniques in graph colouring

Combinatorics and Optimization (CO) 749: Topics in Graph Theory

Topic for winter 2015: advanced techniques in graph colouring

Graph colouring is a storied and important topic of study in graph theory, wherein the vertices of a graph are assigned colours such that no two adjacent vertices receive the same color. From the Four Color Conjecture in the 1852 through Heawood's formula for colouring graphs on surfaces in 1896 to the proof of the Four Color Theorem in 1976, the central and natural problem of determining the chromatic properties of graphs has received international attention.

In the past few decades, many new advancements in graph colouring have been made. Old questions have been generalized and many open conjecture proved. This course will focus on learning these new advanced techniques. The course will also cover some of the many variants of colouring: list colouring, circular colouring, acyclic colouring, edge colouring, etc. Recent results will be mentioned and open problems discussed in the context of these developments and the techniques that enabled their proof. Some of the techniques that will be covered include: discharging, the potential technique, linear isoperimetric inequalities, probabilistic methods, tashkinov trees, etc.

Grading for the course will consist of a few challenging problems sets and a presentation and/or project. A prerequisite for this class is a course in graph theory. A working knowledge of graph theory and a basic exposure to graph coloring will be assumed.

Prerequisite: Graph Theory