Instructors: Marthe Bonamy and Stéphan Thomassé
Prerequisites: Basic notions in graph theory, probability and linear optimization will help but are not mandatory.
Lecture notes: Available here after each session (user: CR2, password: same as for the BBB sessions).
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 ~n0.2-colouring. However, there is no theoretical guarantee that n0.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 (eg 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.
1) Linking chromatic number χ with parameters Δ and ω.
Greedy bounds and Brooks' and Vizing's theorem
Coloring sparse graphs: the probabilistic method
Beyond Mycielski's construction with the probabilistic method
2) χ-bounded graph classes.
Graphs with forbidden induced subgraphs
The dream of polynomial χ-boundedness
3) Generic tools.
The combinatorial Nullstellensatz and polynomial methods
Kernels and Galvin's theorem
Kneser graphs and topological arguments
Planar graphs and the discharging method
Validation: There will be a final exam and two homework assignments (Exercises will be given at each lecture, deadlines for answers are: probably 16th of December for all homework exercises assigned before the 5th of December, and 7th of February for the remaining homework exercises).You may find the assignments of last year here. Please be advised that HMW1 turned out to be more ambitious than we realized, so both assignments this year should be in the line of HMW2 in terms of work involved.
R. Diestel, Graph theory. Springer 1996.
M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method. Springer 2002.
J. Matoušek, Using the Borsuk–Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry. Springer 2003.