Graph coloring is an active field of research that poses many theoretical challenges and has lots of applications in practice. Numerous problems in graph coloring are quite easy to state, but very difficult to prove. A typical example is the problem of coloring planar graphs. It took many years of effort and computer calculations to prove that the vertices of every planar graph can be colored with at most four colors.

Graph coloring involves assigning colors to the elements of a graph such as vertices and edges, on the basis of some constraints. If colors are assigned to a graph so that no two adjacent vertices have the same color, then we call it vertex coloring. Edge coloring is another type of coloring that involves assigning colors to edges so that no two edges have the same color. Vertex coloring and edge coloring are the most common types of graph coloring. However, there are many other types of coloring such as face coloring. This book is meant to be a guide to graph coloring with a focus on algorithms and applications. A basic background in sets, matrices, and enumerative combinatorics is expected for understanding concepts in the book. The book is aimed at students, researchers, and practitioners in areas such as theoretical computer science, optimization, and operations research.

The book is made up of eight chapters and an appendix. The introductory chapter begins with applications such as timetable construction, taxi scheduling, and register allocation for compilers. The author brings in the notions of problem complexity and intractability. Various types of graphs such as complete graphs, bipartite graphs, planar graphs, and grid graphs are examined with a focus on the graph coloring problem. The book takes an algorithmic approach to graph coloring by studying many types of algorithms including greedy algorithms and exact algorithms. A comparison is also made between algorithms. The graph coloring problem may as well be attacked by inexact heuristics and metaheuristics.

The book looks at various types of coloring such as face coloring, edge coloring, precoloring, graph coloring with incomplete information, list coloring, and weighted graph coloring. Applications such as Latin squares, Sudoku puzzles, and circuit testing are discussed as well.

The book emphasizes applications by devoting three chapters to the problems of designing seating plans, sports leagues, and university timetables.

The appendix includes information on compiling using Microsoft Visual Studio and g++. The use of software such as Sage and commercial software for graph coloring is also briefly discussed. Many references to the literature and an index are included at the end of the book. As a bonus, the author provides a suite of graph coloring algorithms that can be obtained from the web [1].

This well-written book will serve as a utilitarian guide to graph coloring and its practical applications. It includes many definitions, theorems, proofs, algorithms, and pointers for further reading. The book will be helpful for teaching courses on graph coloring to students of mathematics and computer science. I strongly recommend it for the intended audience.