Graph Coloring Problems

Rating:
Summary: A concise catalog of theorems and conjectures.
Review: This is a highly technical book that gathers together in one medium-sized volume (less than 300 pages) hundreds of new and classical theorems and conjectures on every conceivable type of graph coloring problem. It is primarily a mathematical treatment in Theorem-Proof style, although the proofs are left to the references (otherwise the book would have been enormous). The book consists of many short sections, each one often less than a page, formally stating a theorem or a conjecture, then briefly summarizing what is known about it, and where the results have been published. As the authors state in the preface, "We did not intend to write a textbook to be read from beginning to end, but rather a catalog suitable for browsing". It seems they have achieved what was intended; it's quite interesting to simply browse through this book.

To give you an idea of the level of the discussion in the text, here is an excerpt from page 1: After a terse definition of vertex coloring and "chromatic number", the authors state that "The existence of the chromatic number follows from the Well-Ordering Theorem of set theory... However, even if it is not assumed that every set has a well-ordering, but maintaining the property that every set has a cardinality, then the statement 'Any finite or infinite graph has a chromatic number' is equivalent to the Axiom of Choice...". If you are unfamiliar with concepts such as well-ordering or the axiom of choice, such a discussion will be of little value to you. However, if you are familiar with these ideas, you will appreciate how quickly the authors jump into meaty discussions. As another example, the chapter on planar graphs begins with a number of excellent questions: "Does there exist a short proof of the four-color theorem...?", "Is there a short argument to demonstrate that the four-color problem is a finite problem?", and "Is there a short argument that proves the existence of a polynomial algorithm to decide if a given planar graph if 4-colorable?", to mention three. The chapter then proceeds to discuss what is currently know about these problems, and many others.

I suspect that the book would be of great interest not only to mathematicians but also computer scientists, as there are numerous discussions/problems on computational complexity. For example, "Does there exist a function g and a polynomial algorithm that for any given input graph G will find a number s, such that the chromatic number of G satisfies s <= X(G) <= g(s)?" (Here X(G) is the chromatic number of graph G.) The authors state that the question was answered affirmatively by Alon in 1993 if X(G) is replaced by "list-chromatic number". This is typical of the problems cataloged in this book: a terse but formally correct statement of a problem followed by what is currently know, with full citations.

The bibliography at the end of each section is extensive, if not daunting, so there should be little problem looking up all relevant literature concerning a given problem. The authors have also set up an on-line archive for up-to-the-minute research results on these problems. This is an excellent reference for those who are interested in serious research in graph coloring. I would not recommend it to undergraduates in computer science or mathematics, nor to those seeking accessible discussions of classic graph algorithms; this is not an introductory text.