Distributed Graph Coloring

Michael Elkin received his Ph.D. in Computer Science and Mathemat ics from the Weizmann Institute, Rehovot, Israel, in 2002. He held po sitions in the Institute for Advanced Study in Princeton and in Yale Uni versity, before joining the Ben-Gurion University of the Negev in 2004. He is an Associate Professor in the Computer Science department in the Ben-Gurion University. His main research interests are distributed algorithms, graph algorithms and metric embeddings. Leonid Barenboim performed his Ph.D. research in Computer Science in Ben-Gurion University of the Negev. His research deals with dis tributed algorithms for symmetry-breaking and synchronization. His re search interests also include graph theory, randomized algorithms and approximation algorithms. He served as a lecturer of a course on im plementation of distributed algorithms and a course on object oriented programming. In 2013 he was accepted to the joint research program of Berkeley and I-CORE that deals with the theoryof big data analysis and large-scale networks

• Acknowledgments.- Introduction.- Basics of Graph Theory.- Basic Distributed Graph Coloring Algorithns.- Lower Bounds.- Forest-Decomposition Algorithms and Applications.- Defective Coloring.- Arbdefective Coloring.- Edge-Coloring and Maximal Matching.- Network Decompositions.- Introduction to Distributed Randomized Algorithms.- Conclusion and Open Questions.- Bibliography.- Authors' Biographies.