Shortcuts
Top of page (Alt+0)
Page content (Alt+9)
Page menu (Alt+8)
Your browser does not support javascript, some WebOpac functionallity will not be available.
.
Default
.
PageMenu
-
Main Menu
-
Simple Search
.
Advanced Search
.
Journal Search
.
Refine Search Results
.
Preferences
.
Search Menu
Simple Search
.
Advanced Search
.
New Items Search
.
Journal Search
.
Refine Search Results
.
Bottom Menu
Help
Italian
.
English
.
German
.
New Item Menu
New Items Search
.
New Items List
.
Links
SISSA Library
.
ICTP library
.
Italian National web catalog (SBN)
.
Trieste University web catalog
.
Udine University web catalog
.
© LIBERO v6.4.1sp220816
Page content
You are here
:
Catalogue Display
Catalogue Display
Graph Colouring and the Probabilistic Method
.
Bookmark this Record
Catalogue Record 48732
.
.
Author info on Wikipedia
.
.
LibraryThing
.
.
Google Books
.
.
Amazon Books
.
Catalogue Information
Catalogue Record 48732
.
Reviews
Catalogue Record 48732
.
British Library
Resolver for RSN-48732
Google Scholar
Resolver for RSN-48732
WorldCat
Resolver for RSN-48732
Catalogo Nazionale SBN
Resolver for RSN-48732
GoogleBooks
Resolver for RSN-48732
ICTP Library
Resolver for RSN-48732
.
Share Link
Jump to link
Catalogue Information
Field name
Details
Dewey Class
519.2
Title
Graph Colouring and the Probabilistic Method ([EBook] /) / by Michael Molloy, Bruce Reed.
Author
Molloy, Michael
Added Personal Name
Reed, Bruce
author.
Other name(s)
SpringerLink (Online service)
Publication
Berlin, Heidelberg : : Springer Berlin Heidelberg : : Imprint: Springer, , 2002.
Physical Details
XIV, 326 p. : online resource.
Series
Algorithms and Combinatorics
0937-5511 ; ; 23
ISBN
9783642040160
Summary Note
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.:
Contents note
1. Colouring Preliminaries -- 2. Probabilistic Preliminaries -- 3. The First Moment Method -- 4. The Lovász Local Lemma -- 5. The Chernoff Bound -- 6. Hadwiger’s Conjecture -- 7. A First Glimpse of Total Colouring -- 8. The Strong Chromatic Number -- 9. Total Colouring Revisited -- 10. Talagrand’s Inequality and Colouring Sparse Graphs -- 11. Azuma’s Inequality and a Strengthening of Brooks’ Theorem -- 12. Graphs with Girth at Least Five -- 13. Triangle-Free Graphs -- 14. The List Colouring Conjecture -- 15. The Structural Decomposition -- 16. ?, ? and ? -- 17. Near Optimal Total Colouring I: Sparse Graphs -- 18. Near Optimal Total Colouring II: General Graphs -- 19. Generalizations of the Local Lemma -- 20. A Closer Look at Talagrand’s Inequality -- 21. Finding Fractional Colourings and Large Stable Sets -- 22. Hard-Core Distributions on Matchings -- 23. The Asymptotics of Edge Colouring Multigraphs -- 24. The Method of Conditional Expectations -- 25. Algorithmic Aspects of the Local Lemma -- References.
System details note
Online access to this digital book is restricted to subscription institutions through IP address (only for SISSA internal users)
Internet Site
http://dx.doi.org/10.1007/978-3-642-04016-0
Links to Related Works
Subject References:
Algorithm Analysis and Problem Complexity
.
Algorithms
.
Combinatorics
.
Computer Science
.
Computers
.
Math Applications in Computer Science
.
Mathematics
.
Probabilities
.
Probability theory and stochastic processes
.
Theory of Computation
.
Authors:
Molloy, Michael
.
Reed, Bruce
.
Corporate Authors:
SpringerLink (Online service)
.
Series:
Algorithms and Combinatorics
.
Classification:
519.2
.
.
ISBD Display
Catalogue Record 48732
.
Tag Display
Catalogue Record 48732
.
Related Works
Catalogue Record 48732
.
Marc XML
Catalogue Record 48732
.
Add Title to Basket
Catalogue Record 48732
.
Catalogue Information 48732
Beginning of record
.
Catalogue Information 48732
Top of page
.
Download Title
Catalogue Record 48732
Export
This Record
As
Labelled Format
Bibliographic Format
ISBD Format
MARC Format
MARC Binary Format
MARCXML Format
User-Defined Format:
Title
Author
Series
Publication Details
Subject
To
File
Email
Reviews
This item has not been rated.
Add a Review and/or Rating
48732
1
48732
-
2
48732
-
3
48732
-
4
48732
-
5
48732
-
Quick Search
Search for