Graph colouring and the probabilistic method / Michael S. Molloy, Bruce Reed.

By:

Molloy, Michael S

Contributor(s):

Reed, Bruce A

Material type: Text

TextSeries: Algorithms and combinatorics ; 23Publication details: Berlin ; New York : Springer, c2002.Description: xiv, 326 p. : ill. ; 24 cmISBN:

9783540421399

Subject(s):

DDC classification:

519.2 21 MOL

LOC classification:

QA612.18 .M65 2002

Online resources:

Contents:

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

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.

Tags from this library: No tags from this library for this title. Log in to add tags.

Average rating: 0.0 (0 votes)

Holdings
Item type	Current library	Collection	Call number	Status	Date due	Barcode
Project book	CUTN Central Library Sciences	Non-fiction	519.2 MOL (Browse shelf(Opens below))	Checked out to Renuka Devi V (20019T)	31/01/2024	48834

Browsing CUTN Central Library shelves, Shelving location: Sciences, Collection: Non-fiction Close shelf browser (Hides shelf browser)

Previous								Next
Previous	519.2 DEG Probability and statistics /	519.2 DEV Probability and statistics for engineering and the sciences /	519.2 MIT Mathematical statistics for economics and business /	519.2 MOL Graph colouring and the probabilistic method /	519.2 PAL Probability and Random Process	519.2 PAL Probability and Random Process	519.2 PAL Probability and Random Process	Next

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.

There are no comments on this title.

to post a comment.