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 (user: CR16, password: same as for the BBB sessions).
Objective:
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.
Course outline:
1) Linking chromatic number χ with parameters Δ and ω.
Greedy bounds and Brooks' and Vizing's theorem
Reed's conjecture
Coloring sparse graphs: the probabilistic method
Mycielski's construction
Beyond Mycielski's construction with the probabilistic method
2)
χ-bounded graph classes.
Perfect graphs
Decomposition theorems
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 was a final exam and two homework assignments (Deadlines: 22nd of December for all homework exercises assigned before the 4th of December, and 15th of February for the remaining homework exercises). The final exam took place on the 28th of January.
Bibliography:
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.