Graph colouring and the probabilistic method (Q5941810)

This monograph provides an accessible and unified treatment of major advances made in graph colouring via the probabilistic method. It is divided into twenty-five chapters. The first two of them are devoted the basic notions of graph colouring and probability theory. Chapters 3-5 present the first moment method, the celebrated Lovász local lemma and the Chernoff bound. These form fundamental tools of the probabilistic method and are used throughout this book. Chapters 6-25 cover the following topics: Hadwiger's conjecture, A first glimpse of total colouring, The strong chromatic number, Total colouring revisited, Talagrand's inequality and colouring sparse graphs, Azuma's inequality and a strengthening of Brooks' theorem, Graphs with girth at least five, Triangle-free graphs, The list colouring conjecture, The structural decomposition, \(\omega\), \(\Delta\) and \(\chi\), Near optimal total colouring: Sparse graphs and general graphs, Generalizations of the local lemma, Finding fractional colourings and large stable sets, Hard-core distributions on matchings, The asymptotics of edge colouring multigraphs, The method of conditional expectations, Algorithmic aspects of the local lemma. 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 researches and graduate students in graph theory, discrete mathematics, theoretical computer science and probability.