Graph Colouring and the Probabilistic Method

by Molloy, Michael S. O.; Reed, Bruce A.

• ISBN13: 9783540421399
• ISBN10: 3540421394
• Format: Hardcover
• Copyright: 2002-01-01
• Publisher: Springer Verlag

Summary

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

Preliminaries
Colouring Preliminaries	p. 3
The Basic Definitions	p. 3
Some Classical Results	p. 5
Fundamental Open Problems	p. 7
A Point of View	p. 9
A Useful Technical Lemma	p. 10
Constrained Colourings and the List Chromatic Number	p. 11
Intelligent Greedy Colouring	p. 12 Exercises
Probabilistic Preliminaries	p. 15
Finite Probability Spaces	p. 15
Random Variables and Their Expectations	p. 17
One Last Definition	p. 19
The Method of Deferred Decisions	p. 20
Exercises	p. 21
Basic Probabilistic Tools
The First Moment Method	p. 27
2-Colouring Hypergraphs	p. 28
Triangle-Free Graphs with High Chromatic Number	p. 29
Bounding the List Chromatic Number as a Functione of the Colouring Number	p. 31
An Open Problem	p. 33
The Cochromatic Number	p. 34
Exercises	p. 36
The Lovasz Local Lemma	p. 39
Constrained Colourings and the List Chromatic Number	p. 41
Exercises	p. 42
The Chernoff Bound	p. 43
Hajos's Conjecture	p. 44
Exercises	p. 46
Vertex Partitions
Hadwiger's Conjecture	p. 49
Step 1: Finding a Dense Subgraph	p. 50
Step 2: Finding a Split Minor	p. 50
Step3: FindingtheMinor	p. 52
Exercises	p. 53
A First Glimpse of Total Colouring	p. 55
The Strong Chromatic Number	p. 61
Exercises	p. 65
Total Colouring Revisited	p. 67
The Idea	p. 67
Some Details	p. 70
The Main Proof	p. 74
Exercises	p. 75
A Naive Colouring Procedure
Talagrand's Inequality and Colouring Sparse Graphs	p. 79
Talagrand's Inequality	p. 79
Colouring Triangle-Free Graphs	p. 83
Colouring Sparse Graphs	p. 86
Strong Edge Colourings	p. 87
Exercises	p. 89
Azuma's Inequality and a Strengthening of Brooks' Theorem	p. 91
Azuma's Inequality	p. 91
A Strengthening of Brooks' Theorem	p. 94
The Probabilistic Analysis	p. 98
Constructing the Decomposition	p. 100
Exercises	p. 103
An Iterative Approach
Graphs with Girth at Least Five	p. 107
Introduction	p. 107
A Wasteful Colouring Procedure	p. 109
The Heart of The Procedure	p. 109
The Finishing Blow	p. 111
The Main Steps of the Proof	p. 112
Most of the Details	p. 115
The Concentration Details	p. 120
Exercises	p. 123
Triangle-Free Graphs	p. 125
An Outline	p. 126
A Modified Procedure	p. 126
Fluctuating Probabilities	p. 128
A Technical Fiddle	p. 130
A Complication	p. 131
The Procedure	p. 131
Dealing with Large Probabilities	p. 131
The Main Procedure	p. 132
The Final Step	p. 132
The Parameters	p. 133
Expectation and Concentration	p. 136
Exercises	p. 138
The List Colouring Conjecture	p. 139
A Proof Sketch	p. 140
Preliminaries	p. 140
The Local Structure	p. 140
Rates of Change	p. 141
The Preprocessing Step	p. 142
Choosing Reserve(e)	p. 144
The Expected Value Details	p. 145
The Concentration Details	p. 149
The Wrapup	p. 151
Linear Hypergraphs	p. 152
Exercises	p. 153
A Structural Decomposition
The Structural Decomposition	p. 157
Preliminary Remarks	p. 157
The Decomposition	p. 157
Partitioning the Dense Sets	p. 160
Graphs with $$ Near $$	p. 165
Generalizing Brooks' Theorem	p. 165
Blowing Up a Vertex	p. 166
Exercises	p. 167
$$,$$ and $$	p. 169
The Modified Colouring Procedure	p. 171
An Extension of Talagrand's Inequality	p. 172
Strongly Non-Adjacent Vertices	p. 173
Many Repeated Colours	p. 175
The Proof of Theorem 16.5	p. 179
Proving the Harder Theorems	p. 181
Two Proofs	p. 182
Exercises	p. 184
Near Optimal Total Colouring I: Sparse Graphs	p. 185
Introduction	p. 185
The Procedure	p. 187
The Analysis of the Procedure188
The Final Phase	p. 191
Near Optimal Total Colouring II: General Graphs	p. 195
Introduction	p. 195
Phase I: An Initial Colouring	p. 198
Ornery Sets	p. 198
The Output of Phase I	p. 200
A Proof Sketch	p. 201
Phase II: Colouring the Dense Sets	p. 206
$$(i) is Non-Empty	p. 207
Our Distribution is Nearly Uniform	p. 208
Completing the Proof	p. 209
The Temporary Colours	p. 210
Step 1	p. 211
Step2	p. 215
Phase IV - Finishing the Sparse Vertices	p. 216
The Ornery Set Lemmas	p. 217
Sharpening our Tools
Generalizations of the Local Lemma	p. 221
Non-Uniform Hypergraph Colouring	p. 222
More Frugal Colouring	p. 224
Acyclic Edge Colouring	p. 225
Proofs	p. 226
The Lopsided Local Lemma	p. 228
Exercises	p. 229
A Closer Look at Talagrand's Inequality	p. 231
The Original Inequality	p. 231
More Versions	p. 234
Exercises	p. 236
Colour Assignment via Fractional Colouring
Finding Fractional Colourings and Large Stable Sets	p. 239
Fractional Colouring	p. 239
Finding Large Stable Setsin Triangle-Free Graphs	p. 242
Fractionally, $$ $$	p. 244
Exercises	p. 246
Hard-Core Distributions on Matchings	p. 247
Hard-Core Distributions	p. 247
Hard-Core Distributions from Fractional Colourings	p. 249
The Mating Map	p. 252
An Independence Result	p. 254
More Independence Results	p. 260
The Asymptotics of Edge Colouring Multigraphs	p. 265
Assigning the Colours	p. 265
Hard-Core Distributions and Approximate Independence	p. 266
The Chromatic Index	p. 267
The List Chromatic Index	p. 270
Analyzing an Iteration	p. 272
Analyzing a Different Procedure	p. 274
One More Tool	p. 277
Comparing the Procedures	p. 279
Proving Lemma 23.9	p. 282
Algorithmic Aspects
The Method of Conditional Expectations	p. 287
The Basic Ideas	p. 287
An Algorithm	p. 288
Generalized Tic-Tac-Toe	p. 289
Proof of Lemma 24.3	p. 291
Algorithmic Aspects of the Local Lemma	p. 295
The Algorithm	p. 296
The Basics	p. 296
Further Details	p. 299
A Different Approach	p. 300
Applicability of the Technique	p. 301
Further Extensions	p. 303
Extending the Approach	p. 304
3-Uniform Hypergraphs	p. 305
k-Uniform Hypergraphs with k > =4	p. 308
The General Technique	p. 310
Exercises	p. 312
References	p. 314
Index	p. 323
Table of Contents provided by Publisher. All Rights Reserved.