Review of

Jensen and Toft: Graph Coloring Problems, Wiley 1995

by Kenneth I. Appel.

Consider our options when we decide that a certain area of mathematics looks interesting and we want to find out what has been done in the area and what open problems are currently being studied. In many fields the only reasonable approach is to read one or more standard reference texts and then look through Mathematical Reviews under the appropriate subject code to see what has been done recently. To do this is virtuous and rewarding and is a hallmark of a serious scholar. Often, however, people want to learn just enough about a field to see if they are seriously enough interested to invest a large amount of time in becoming expert enough to deal with research problems in the area.

A graduate student in a reasonably diversified department can often find some congenial professor-expert in the area and ask a number of questions. Often these questions lead to the matching of student with thesis adviser, and a career is begun. Experienced mathematicians are used to consulting colleagues to talk about areas that look interesting. Without the proximity of a colleague who is expert in the area, the initial readings can be somewhat haphazard. That is where a book suggesting interesting open problems can serve the useful purpose of pointing out new directions.

Jensen and Toft have written just such a book for an interesting class of problems in graph theory. They presume of the reader little more than familiarity with the basic definitions of graph theory, and they present two hundred unsolved problems in seventeen chapters, each chapter devoted to a class of problems.

For almost a century and a half, a Holy Grail of graph theory has been a simple incisive proof of the Four Color Theorem. It has troubled our profession that a problem that can be understood by a school child has yet to be solved in a way that better illuminates the reason that only four colors are needed for planar maps. The feelings of many mathematicians were summed up for me by Herb Wilf's response to being told that it appeared that one could prove the theorem by a long reducibility argument which used computers to test the reducibility of a large number of configurations. He simply said, ``God would not allow such a beautiful theorem to have such an ugly proof.''

It may or may not be true that the Grail exists, but the search for it has created a tremendous amount of interesting mathematics at almost every level of depth. Many techniques invented to help in the search for the hoped-for simple proof have proved extremely useful in attacking problems in pure and applied mathematics and in computer science. Definitions used originally for creating these techniques have been generalized and in the hands of the masters like Erdős, Tutte, Lovász and others have led to results of great elegance and left many fascinating and tantalizing problems.

Of course, many problems of coloring involve the question of how to color things efficiently. These questions lead to consideration of computational complexity of algorithms for performing tasks which, while of great fascination, really cannot legitimately be thought of as basically being derived from the Grail, but there are many other questions that can be. Why has no one been able to extend Heawood's 1890 upper-bound argument for surfaces of genus greater than zero to the sphere by some clever modification? Why haven't the elegant techniques of chromatic polynomials provided the neat argument? In attacking such questions, mathematicians have come up with many related questions. In the 1880's Tait hoped to find a proof by considering edge-three colorings. This work led to many questions about edge colorings not at all related to the Four Color Theorem. The assumption that a proof would need to be inductive has led to a great deal of study of critical graphs, those dragonlike potential minimal counterexamples to be pierced by Excalibur.

The authors list problems derived from these and many more approaches and some problems that arise simply from thinking hard about partitioning sets into subsets with properties that can be described in terms of colorings. Each of the two hundred problems is stated in the appropriate chapter and is followed by the partial results that have been obtained, by whom they have been obtained, and where they have been published. In many instances the results are explained in some detail and traced historically. As might be expected, chapters dealing with problems in the authors' research areas---for example, the chapter on the Conjectures of Hadwiger and Hajós and the chapter on critical graphs---contain a wealth of historic detail and great insight into the status of some very difficult problems.

Each chapter provides appropriate definitions, and there are chapter-by-chapter bibliographies. The bibliographies are excellent and take up sixty pages of the 295-page book. While a certain number of articles are listed in the bibliographies of more than one chapter, most are not.

To try to keep the book from becoming dated, the authors have created an ftp archive with World Wide Web access to provide access to new and updated information on these problems as it becomes available. Thus, the combination of book and archive should continue to be a valuable source of information for many years.

Back to Graph Coloring Problems homepage