Ebook: Graph Colouring and the Probabilistic Method

---

Content:
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

---

Content:
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
....