The Four-Color Problem

by Thomas L. Saaty, Paul G. Kainen

Paperback book. Approximately 5.5 x 8 sized book. A total of 217 pages. 1986, Dover Edition, first published in 1986, is an unbridged corrected republication of the work originally published by the McGraw-Hill International Book Company, NY, 1977, USA. The spine is tight, pages are clean and easy to read. Dover Publications, Inc. , NY. The boards show normal shelf wear. Bottom front board has a crease or fine line and bottom corner is worn or rubbed slightly. There is a tiny, very small, light brown stain about midway at the bottom of the book that is barely noticeable on the page edges, however does not bleed into the pages. A couple of minor finger line small creases on the back board where the previous owner held the book and read it. A good price for this book by Thomas L. Saaty and Paul C. Kainen. The following is taken from the prefix of this "We believe that mathematicians get more excitement by doing the entire job of proving the existence of solutions and then constructing them by themselves than they do by relying on the computer as a substantial partner in the undertaking. Still, ambitious experts in artificial intelligence are telling us that it will not be long before computers will be doing all that we do, better and faster." It " We hope this book will continue to evoke interest in the four color problem, in its computer aided solution, and perhaps in finding an alternative way to prove it. By the way, a natural follow up would be a four color algorithm." A very interesting book and affordably priced.

Genres: Mathematics

217 pages, Paperback

First published December 1, 1977

Reviews

[Manny · Rating 4 out of 5]

The Four-Color Conjecture is one of the most famous problems in mathematics: can you always color a map with only four colors, so that no two adjoining countries have the same color? People tried for over a century to solve it, without success.

Saaty and Kainen's book was meant to give an overview of the state of play, but then an extraordinary event occurred. To quote their preface:

A funny thing happened to this book on the way to the publisher. More than two years ago, we had completed the manuscript of a book entitled Assaults on the Four-Color Conjecture... Our original book was oriented towards the variety of approaches with which the four-color conjecture (4CC for brevity) has been investigated. The reader can well imagine our mixed reactions to the announcement, in the summer of 1976, that the 4CC had been proved - by a computer, no less.

They rewrote the book to focus on the newly discovered solution, and it's very interesting. People had been searching for an elegant, insightful proof, but the key turned out to be to use a machine to turn the problem into hundreds of special cases, and solve each one individually. The resulting proof is so long that only a machine can hope to be able to check its correctness.

Mathematicians were initially skeptical, and some of them refused to admit that the problem had genuinely been solved. But I've just been looking around for more recent publications, and the proof has stood the test of time. A couple of people identified minor errors, and they have all been quickly addressed. Now almost everyone agrees it's good.

Another little victory for the machines in their ongoing battle with human beings. I think this was the first example of an unquestionably deep and interesting concept which a computer could understand and a human couldn't.

[Neil · Rating 5 out of 5]

It would be enough to have the excellent history of the conjecture and explication of Appel & Haken's theorem, but the meaty discussion of outstanding questions in graph coloring is what really makes this volume shine. The work on the roots of chromials is especially great.