Graph colouring and the probabilistic method /
Molloy, Michael S.
Graph colouring and the probabilistic method / Michael S. Molloy, Bruce Reed. - Berlin ; New York : Springer, c2002. - xiv, 326 p. : ill. ; 24 cm. - Algorithms and combinatorics, 23 0937-5511 ; .
Includes bibliographical references (p. [315]-321) and index.
Front Matter
Pages I-XIV
PDF
Preliminaries
Front Matter
Pages 1-1
PDF
Colouring Preliminaries
Michael Molloy, Bruce Reed
Pages 3-14
Probabilistic Preliminaries
Michael Molloy, Bruce Reed
Pages 15-24
Basic Probabilistic Tools
Front Matter
Pages 25-25
PDF
The First Moment Method
Michael Molloy, Bruce Reed
Pages 27-37
The Lovász Local Lemma
Michael Molloy, Bruce Reed
Pages 39-42
The Chernoff Bound
Michael Molloy, Bruce Reed
Pages 43-46
Vertex Partitions
Front Matter
Pages 47-47
PDF
Hadwiger’s Conjecture
Michael Molloy, Bruce Reed
Pages 49-53
A First Glimpse of Total Colouring
Michael Molloy, Bruce Reed
Pages 55-59
The Strong Chromatic Number
Michael Molloy, Bruce Reed
Pages 61-65
Total Colouring Revisited
Michael Molloy, Bruce Reed
Pages 67-75
A Naive Colouring Procedure
Front Matter
Pages 77-78
PDF
Talagrand’s Inequality and Colouring Sparse Graphs
Michael Molloy, Bruce Reed
Pages 79-89
Azuma’s Inequality and a Strengthening of Brooks’ Theorem
Michael Molloy, Bruce Reed
Pages 91-103
An Iterative Approach
Front Matter
Pages 105-105
PDF
Graphs with Girth at Least Five
Michael Molloy, Bruce Reed
Pages 107-124
Triangle-Free Graphs
Michael Molloy, Bruce Reed
Pages 125-138
The List Colouring Conjecture
Michael Molloy, Bruce Reed
Pages 139-153
A Structural Decomposition
Front Matter
Pages 155-156
PDF
The Structural Decomposition
Michael Molloy, Bruce Reed
Pages 157-168
ω, Δ and χ
Michael Molloy, Bruce Reed
Pages 169-184
Near Optimal Total Colouring I: Sparse Graphs
Michael Molloy, Bruce Reed
Pages 185-193
Near Optimal Total Colouring II: General Graphs
Michael Molloy, Bruce Reed
Pages 195-218
Sharpening our Tools
Front Matter
Pages 219-219
PDF
Generalizations of the Local Lemma
Michael Molloy, Bruce Reed
Pages 221-229
A Closer Look at Talagrand’s Inequality
Michael Molloy, Bruce Reed
Pages 231-236
Colour Assignment via Fractional Colouring
Front Matter
Pages 237-237
PDF
Finding Fractional Colourings and Large Stable Sets
Michael Molloy, Bruce Reed
Pages 239-246
Hard-Core Distributions on Matchings
Michael Molloy, Bruce Reed
Pages 247-264
The Asymptotics of Edge Colouring Multigraphs
Michael Molloy, Bruce Reed
Pages 265-283
Algorithmic Aspects
Front Matter
Pages 285-285
PDF
The Method of Conditional Expectations
Michael Molloy, Bruce Reed
Pages 287-293
Algorithmic Aspects of the Local Lemma
Michael Molloy, Bruce Reed
Pages 295-313
Back Matter
Pages 315-326
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.
9783540421399
2001055101
Graph coloring.
Combinatorial analysis.
Probabilities.
QA612.18 / .M65 2002
519.2 / MOL
Graph colouring and the probabilistic method / Michael S. Molloy, Bruce Reed. - Berlin ; New York : Springer, c2002. - xiv, 326 p. : ill. ; 24 cm. - Algorithms and combinatorics, 23 0937-5511 ; .
Includes bibliographical references (p. [315]-321) and index.
Front Matter
Pages I-XIV
Preliminaries
Front Matter
Pages 1-1
Colouring Preliminaries
Michael Molloy, Bruce Reed
Pages 3-14
Probabilistic Preliminaries
Michael Molloy, Bruce Reed
Pages 15-24
Basic Probabilistic Tools
Front Matter
Pages 25-25
The First Moment Method
Michael Molloy, Bruce Reed
Pages 27-37
The Lovász Local Lemma
Michael Molloy, Bruce Reed
Pages 39-42
The Chernoff Bound
Michael Molloy, Bruce Reed
Pages 43-46
Vertex Partitions
Front Matter
Pages 47-47
Hadwiger’s Conjecture
Michael Molloy, Bruce Reed
Pages 49-53
A First Glimpse of Total Colouring
Michael Molloy, Bruce Reed
Pages 55-59
The Strong Chromatic Number
Michael Molloy, Bruce Reed
Pages 61-65
Total Colouring Revisited
Michael Molloy, Bruce Reed
Pages 67-75
A Naive Colouring Procedure
Front Matter
Pages 77-78
Talagrand’s Inequality and Colouring Sparse Graphs
Michael Molloy, Bruce Reed
Pages 79-89
Azuma’s Inequality and a Strengthening of Brooks’ Theorem
Michael Molloy, Bruce Reed
Pages 91-103
An Iterative Approach
Front Matter
Pages 105-105
Graphs with Girth at Least Five
Michael Molloy, Bruce Reed
Pages 107-124
Triangle-Free Graphs
Michael Molloy, Bruce Reed
Pages 125-138
The List Colouring Conjecture
Michael Molloy, Bruce Reed
Pages 139-153
A Structural Decomposition
Front Matter
Pages 155-156
The Structural Decomposition
Michael Molloy, Bruce Reed
Pages 157-168
ω, Δ and χ
Michael Molloy, Bruce Reed
Pages 169-184
Near Optimal Total Colouring I: Sparse Graphs
Michael Molloy, Bruce Reed
Pages 185-193
Near Optimal Total Colouring II: General Graphs
Michael Molloy, Bruce Reed
Pages 195-218
Sharpening our Tools
Front Matter
Pages 219-219
Generalizations of the Local Lemma
Michael Molloy, Bruce Reed
Pages 221-229
A Closer Look at Talagrand’s Inequality
Michael Molloy, Bruce Reed
Pages 231-236
Colour Assignment via Fractional Colouring
Front Matter
Pages 237-237
Finding Fractional Colourings and Large Stable Sets
Michael Molloy, Bruce Reed
Pages 239-246
Hard-Core Distributions on Matchings
Michael Molloy, Bruce Reed
Pages 247-264
The Asymptotics of Edge Colouring Multigraphs
Michael Molloy, Bruce Reed
Pages 265-283
Algorithmic Aspects
Front Matter
Pages 285-285
The Method of Conditional Expectations
Michael Molloy, Bruce Reed
Pages 287-293
Algorithmic Aspects of the Local Lemma
Michael Molloy, Bruce Reed
Pages 295-313
Back Matter
Pages 315-326
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.
9783540421399
2001055101
Graph coloring.
Combinatorial analysis.
Probabilities.
QA612.18 / .M65 2002
519.2 / MOL