Graph Colouring and the Probabilistic Method
326 pages, parution le 28/11/2001
Résumé
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 the Lovasz Local Lemma and
Concentration Inequalities developed by Talagrand.
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 gentle introduction to the probabilistic method will be useful to researchers and graduate students in graph theory, discrete mathematics, theoretical computer science and probabilists.
Contents
- Preliminaries
- Basic Probabilistic Tools
- Vertex Partitions
- A Naive Colouring Procedure
- An Iterative Approach
- Structural Decomposition
- Sharpening our Tools
- Colour Assignement via Fractional Colouring
- Algorithmic Aspects
- References
- Index
L'auteur - Bruce A. Reed
CNRS, Paris, France
Caractéristiques techniques
| PAPIER | |
| Éditeur(s) | Springer |
| Auteur(s) | Michael Molloy, Bruce A. Reed |
| Parution | 28/11/2001 |
| Nb. de pages | 326 |
| Format | 15,5 x 24 |
| Couverture | Relié |
| Poids | 650g |
| Intérieur | Noir et Blanc |
| EAN13 | 9783540421399 |
Avantages Eyrolles.com
Livraison à partir de 0,01 € en France métropolitaine
Paiement en ligne SÉCURISÉ
Livraison dans le monde
Retour sous 15 jours
+ d'un million et demi de livres disponibles
Consultez aussi
- Les meilleures ventes en Graphisme & Photo
- Les meilleures ventes en Informatique
- Les meilleures ventes en Construction
- Les meilleures ventes en Entreprise & Droit
- Les meilleures ventes en Sciences
- Les meilleures ventes en Littérature
- Les meilleures ventes en Arts & Loisirs
- Les meilleures ventes en Vie pratique
- Les meilleures ventes en Voyage et Tourisme
- Les meilleures ventes en BD et Jeunesse
