Author | Molloy, Michael. author |
---|---|
Title | Graph Colouring and the Probabilistic Method [electronic resource] / by Michael Molloy, Bruce Reed |
Imprint | Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2002 |
Connect to | http://dx.doi.org/10.1007/978-3-642-04016-0 |
Descript | XIV, 326 p. online resource |
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