Graph Colouring and the Probabilistic Method

By: Michael Molloy, Bruce Reed

Write A Review

Hardcover | 20 November 2001

Sorry, we are not able to source the book you are looking for right now.

We did a search for other books with a similar title, however there were no matches. You can try selecting from a similar category, click on the author's name, or use the search box above to find your book.

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.

Industry Reviews

From the reviews of the first edition:

"The presented book contains many ... chapters, each of which presents a proof technique and apply that for a certain graph coloring problem. ... The book ends with a vast bibliography. We think that this well-written monograph will serve as a main reference on the subject for years to come." (Janos Barat, Acta Scientiarum Mathematicarum, Vol. 69, 2003)

"The book is a pleasure to read; there is a clear, successful attempt to present the intuition behind the proofs, making even the difficult, recent proofs of important results accessible to potential readers. ... The book is highly recommended to researchers and graduate students in graph theory, combinatorics, and theoretical computer science who wish to have this ability." (Noga Alon, SIAM Review, Vol. 45 (2), 2003)

"The probabilistic method in graph theory was initiated by Paul Erdos in 1947 ... . This book is an introduction to this powerful method. ... The book is well-written and brings the researcher to the frontiers of an exciting field." (M.R. Murty, Short Book Reviews, Vol. 23 (1), April, 2003)

"This monograph provides an accessible and unified treatment of major advances made in graph colouring via the probabilistic method. ... Many exercises and excellent remarks are presented and discussed. Also very useful is the list of up-to-date references for current research. This monograph will be useful both to researchers and graduate students in graph theory, discrete mathematics, theoretical computer science and probability." (Jozef Fiamcik, Zentralblatt MATH, Vol. 987 (12), 2002)

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

Orders over $79.00 qualify for free shipping.

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

You Can Find This Book In

Non-Fiction Mathematics Combinatorics & Graph Theory Probability & Statistics Medicine Medicine in General Computing & I.T.Computer Science Mathematical Theory of Computation

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.

Graph Colouring and the Probabilistic Method

Industry Reviews

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Medicine in General

Ferment

The Life-Changing Power of Microbes

Principles of Anatomy and Physiology

3rd Asia Pacific Edition

Enhancing Women's Wellbeing During Matrescence, Motherhood, and Perinatal Transitions

1st Edition - An Evidence-based Guide for Occupational Therapists

Genius Gut

The Life-Changing Science of Eating for Your Second Brain

Havard's Nursing Guide to Drugs

11th Edition

Netter's Anatomy Coloring Book

3rd edition

Liver Cleansing Diet (Revised Edition)

Love Your Liver and Live Longer

It's OK That You're Not OK

Meeting Grief and Loss in a Culture That Doesn't Understand

Brain Changer

Good Mental Health Diet

The Mediterranean Diet Cookbook for Beginners

Mean Plans, Tips and Tricks, and Over 75 Recipes to Get You Started

You Called an Ambulance for What?

Forever Strong

A New, Science-Based Strategy for Aging Well

The Australian Policy Handbook

7th Edition - A Practical Guide to the Policymaking Process

Talley & O'Connor's Clinical Examination 2 volume set

9th Edition

Toxic Superfoods

The Hidden Toxin in 'Superfoods' That's Making You Sick--and How to Feel Better

Taking Charge of Adult ADHD: 2 Edition

Proven Strategies to Succeed at Work, at Home, and in Relationships

Dopamine Nation

Finding Balance in the Age of Indulgence

Good Energy

The Surprising Connection Between Glucose, Metabolism and Limitless Health

The Age of Diagnosis

How the Overdiagnosis Epidemic is Making Us Sick - THE SUNDAY TIMES BESTSELLER

The Food For Life Cookbook

100+ Recipes Created with ZOE

Live to Eat

The food you crave, the nutrition you need: The instant #1 Sunday Times bestseller

You Went to Emergency for What?

Bizarre, bloody and baffling true stories from the hospital ED

Renal Diet Cookbook for the Newly Diagnosed

The Complete Guide to Managing Kidney Disease and Avoiding Dialysis

The Galveston Diet

Your Ultimate Menopause Health Plan

This product is categorised by