Prerequisites: Basic notions in graph theory.
Objective: Graph coloring is one of the most studied and least understood concepts in graph theory. This course aims to consider the structure of graphs of high chromatic number and to present a broad overview of the proof techniques in the field.
1) χ, Δ and ω.
Greedy bounds and Brooks' 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 Nustellensatz and polynomial methods
Kernels and Galvin's theorem
Kneser graphs and topological arguments
Planar graphs and the discharging method
Validation: There will be a written final exam and a homework assignment.
M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method. Springer 2002.