R. M. R. Lewis - Guide to Graph Colouring: Algorithms and Applications

More information about this series at http://www.springer.com/series/3191

This Springer imprint is published by the registered company Springer Nature Switzerland AG

The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland

Graph colouring is one of those rare examples in the mathematical sciences of a problem that, while easy to state and visualise, has many aspects that are exceptionally difficult to solve.

In this book, our goal is to examine graph colouring as an algorithmic problem, with a strong emphasis on implementation and practical application. To these ends, in addition to providing a theoretical treatment of the problem, we also dedicate individual chapters to real-world problems that can be tackled via graph colouring techniques. These include designing sports schedules, solving Sudoku puzzles, timetabling lectures at a university, and creating seating plans.

Portable source code for all of the algorithms considered in this book is also available for free download.

The first chapter of this book is kept deliberately light; it gives a brief tour of the graph colouring problem, avoids jargon, and gives plenty of illustrated examples.

In Chap. , we discover that graph colouring is a type of intractable problem, meaning that it usually needs to be tackled using inexact heuristic algorithms. To reach this conclusion, we introduce the topics of problem complexity, polynomial transformations, and -completeness. We also review several graph topologies that are easy to colour optimally.

Chapter of this book starts with some theory and uses various techniques to derive bounds on the chromatic number of graphs. It then looks at five well-established constructive heuristics for graph colouring (including the Greedy, DSatur, and RLF algorithms) and analyses their relative performance. Source code for these algorithms is provided.

The intention of Chap. is to give the reader an overview of the different strategies available for graph colouring, including both exact and heuristic methods. Techniques considered include backtracking, integer programming, column generation, and various metaheuristics. No prior knowledge of these techniques is assumed. We also describe ways in which graph colouring problems can be reduced in size and broken into smaller parts, helping to improve algorithm performance.

Chapter gives an in-depth analysis of six high-performance algorithms for the graph colouring problem. The performance of these algorithms is compared using several different problem types, including random, flat, scale-free, planar, and timetabling graphs. Source code for each of these algorithms is also provided.

Chapter considers several problems, both theoretical and practical, that can be expressed through graph colouring principles. Initial sections focus on special cases of the graph colouring problem, including map colouring (together with a history of the Four Colour Theorem), edge colouring, Latin squares, and Sudoku puzzles. The problems of colouring graphs where only limited information about connectivity is known, or where a graph is subject to change over time, are also considered, as are some natural extensions to graph colouring such as list colouring, equitable graph colouring, weighted graph colouring, and chromatic polynomials.

The final three chapters of this book examine three separate case studies in which graph colouring techniques can be used to find high-quality solutions to real-world problems. Chapter looks at timetabling in educational establishments. Each of these chapters is written so that, to a large extent, they can be read independently of the other chapters of this book.

This book is written for anyone with a background in mathematics, computer science, operational research, or management science. Initial sections are particularly appropriate for undergraduate learning and teaching; later sections are more suited for postgraduate and research levels.

This text has been written with the presumption that the reader has no previous experience of graph colouring or graph theory more generally. However, elementary knowledge of the notation and concepts surrounding sets, matrices, and enumerative combinatorics (particularly combinations and permutations) is assumed.

All algorithms reviewed and tested in this book are available for free download at http://www.rhydlewis.eu/resources/gCol.zip . These implementations are written in C++ and can be compiled on Windows, macOS, and Linux. Full instructions on how to do this are provided in Appendix A. Readers are invited to experiment with these algorithms as they make their way through this book.

This book also shows how graph colouring problems can be generated and tackled using Sage and Python. Both of these programming languages are free to download. We also show how graph colouring problems can be solved via linear programming software, in this case using the commercial software FICO Xpress.