Topics in Algorithmic Graph Theory

Lowell W. Beineke is the Jack W. Schrey Professor Emeritus of Mathematics at Purdue University Fort Wayne. He has written over a hundred papers in graph theory and has served as Editor of The College Mathematics Journal. In addition to four previous volumes in this series, Robin Wilson and he have jointly edited five other books in the field. Recent honours include having an award of the College of Arts and Sciences at his university named after him, being entered into the Purdue University Book of Great Teachers, and receiving a Meritorious Service award from the Mathematical Association of America. He also received a Lifetime Service Award from Who's Who in America. Martin Charles Golumbic is an Emeritus Professor of Computer Science at the University of Haifa and founder of the Caesarea Edmond Benjamin de Rothschild Institute for Interdisciplinary Applications of Computer Science. He is the founding Editor-in-Chief of the journal Annals of Mathematics and Artificial Intelligence. The books he has written include Algorithmic Graph Theory and Perfect Graphs, Tolerance Graphs (with Ann Trenk), Fighting Terror Online: The Convergence of Security, Technology, and the Law and The Zeroth Book of Graph Theory: An Annotated Translation of Les Réseaux (ou Graphes) by André Sainte-Laguë. He is a Foundation Fellow of the Institute of Combinatorics and its Applications, a Fellow of the European Artificial Intelligence society EurAI, and a member of the Academia Europaea, honoris causa. Robin J. Wilson is an Emeritus Professor of Pure Mathematics at the Open University, UK, and of Geometry at Gresham College, London, and is a former Fellow of Keble College, Oxford. He has written and edited over forty books on graph theory, combinatorics and the history of mathematics, including Introduction to Graph Theory and Four Colours Suffice. A former President of the British Society for the History of Mathematics, he has won prizes from the Mathematical Association of America for his expository writing and was awarded the 2017 Stanton Medal of the Institute of Combinatorics and its Applications for his outreach activities in combinatorics.

• Foreword Martin Charles Golumbic; Preface Lowell W. Beineke and Robin J. Wilson; Preliminaries Lowell W. Beineke, Martin Charles Golumbic and Robin J. Wilson; 1. Graph Algorithms Martin Charles Golumbic; 2. Graph Colouring Variations Alain Hertz and Bernard Ries; 3. Total Colouring Celina M. H. de Figueiredo; 4. Testing of Graph Properties Ilan Newman; 5. Cliques, Colouring and Satisfiability: From Structure to Algorithms Vadim Lozin; 6. Chordal Graphs Martin Charles Golumbic; 7. Dually and Strongly Chordal Graphs Andreas Brandstädt and Martin Charles Golumbic; 8. Leaf Powers Christian Rosenke, Van Bang Le and Andreas Brandstädt; 9. Split Graphs Karen L. Collins and Ann N. Trenk; 10. Strong Cliques and Stable Sets Martin Milanič; 11. Restricted Matchings Maximilian Fürst and Dieter Rautenbach; 12. Covering Geometric Domains Gila Morgenstern; 13. Graph Homomorphisms Pavol Hell and Jaroslav Nešetřil; 14. Sparsity and Model Theory Patrice Ossona de Mendez; 15. Extremal Vertex-sets Serge Gaspers; Notes on Contributors; Index.