# CR16: Graphs with high chromatic number

• 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

• 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.