Chromatic number is one of the most studied and least understood parameter in graph theory, both from the structural and the algorithmic point of view. Given a 3-colorable graph G on n vertices, but without access to a 3-colouring of it, the best known polynomial algorithm computes a ~n^0.2-colouring. However, there is no theoretical guarantee that n^0.2 is best here — for all we know it could be replaced with log n.

This algorithmic failure reflects the (structural) fact that graphs with high chromatic number can be extremely simple on a small scale — for example, they can “look like a tree” around every vertex. To construct such objects, Erdős developed the so-called probabilistic method, which proved to be useful for a wide range of graph-theoretic problems. However, the difficulty (and beauty) of chromatic number is that constructions of locally simple/globally hard graphs also arise from other areas: for instance the Borsuk-Ulam theorem directly provides graphs with high chromatic number in which all small subgraphs are bipartite (2-colorable).

This question “What makes the chromatic number large?” has several starkly different answers and seems to be very difficult. Ideally, we would like to tie this elusive parameter to other tamer parameters, like the maximum degree, even to some that are still hard to compute but present a local structure, like the maximum size of a clique (clique number). This is impossible in general, but we investigate specific graph classes, such as perfect graphs or minor closed classes (e.g. planar), where it can be tied to a parameter or another.

In this course, we will keep an eye on both structural results and (sometimes!) efficient algorithms.