Graph Colouring and the Probabilistic Method

Michael Molloy, Bruce Reed (auth.)3540421394, 9783540421399

Over the past decade, many major advances have been made in the field of graph colouring via the probabilistic method. This monograph provides an accessible and unified treatment of these results, using tools such as the Lovasz Local Lemma and Talagrand’s concentration inequality.The topics covered include: Kahn’s proofs that the Goldberg-Seymour and List Colouring Conjectures hold asymptotically; a proof that for some absolute constant C, every graph of maximum degree Delta has a Delta+C total colouring; Johansson’s proof that a triangle free graph has a O(Delta over log Delta) colouring; algorithmic variants of the Local Lemma which permit the efficient construction of many optimal and near-optimal colourings.This begins with a gentle introduction to the probabilistic method and will be useful to researchers and graduate students in graph theory, discrete mathematics, theoretical computer science and probability.

---

Table of contents :
Front Matter….Pages I-XIV
Front Matter….Pages 1-1
Colouring Preliminaries….Pages 3-14
Probabilistic Preliminaries….Pages 15-24
Front Matter….Pages 25-25
The First Moment Method….Pages 27-37
The Lovász Local Lemma….Pages 39-42
The Chernoff Bound….Pages 43-46
Front Matter….Pages 47-47
Hadwiger’s Conjecture….Pages 49-53
A First Glimpse of Total Colouring….Pages 55-59
The Strong Chromatic Number….Pages 61-65
Total Colouring Revisited….Pages 67-75
Front Matter….Pages 77-78
Talagrand’s Inequality and Colouring Sparse Graphs….Pages 79-89
Azuma’s Inequality and a Strengthening of Brooks’ Theorem….Pages 91-103
Front Matter….Pages 105-105
Graphs with Girth at Least Five….Pages 107-124
Triangle-Free Graphs….Pages 125-138
The List Colouring Conjecture….Pages 139-153
Front Matter….Pages 155-156
The Structural Decomposition….Pages 157-168
ω, Δ and χ….Pages 169-184
Near Optimal Total Colouring I: Sparse Graphs….Pages 185-193
Near Optimal Total Colouring II: General Graphs….Pages 195-218
Front Matter….Pages 219-219
Generalizations of the Local Lemma….Pages 221-229
A Closer Look at Talagrand’s Inequality….Pages 231-236
Front Matter….Pages 237-237
Finding Fractional Colourings and Large Stable Sets….Pages 239-246
Hard-Core Distributions on Matchings….Pages 247-264
The Asymptotics of Edge Colouring Multigraphs….Pages 265-283
Front Matter….Pages 285-285
The Method of Conditional Expectations….Pages 287-293
Algorithmic Aspects of the Local Lemma….Pages 295-313
Back Matter….Pages 315-326