Winter Driving Best Books of the Month Valentine's Day Shop Learn more nav_sap_SWP_6M_fly_beacon King easycohice_2016 All-New Amazon Fire TV Beauty V-Day Valentine's Day Cards Create an Amazon Wedding Registry Amazon Gift Card Offer chiraq chiraq chiraq  Amazon Echo All-New Fire Kindle Paperwhite Prime Exclusive Savings in Video Games Shop Now SnS
Customer Review

13 of 13 people found the following review helpful
5.0 out of 5 stars A concise catalog of theorems and conjectures., July 14, 2003
This review is from: Graph Coloring Problems (Paperback)
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.
Help other customers find the most helpful reviews 
Was this review helpful to you? Yes No

Be the first person to comment on this review.

[Add comment]
Post a comment
To insert a product link use the format: [[ASIN:ASIN product-title]] (What's this?)
Amazon will display this name with all your submissions, including reviews and discussion posts. (Learn more)
This badge will be assigned to you and will appear along with your name.
There was an error. Please try again.
Please see the full guidelines here.

Official Comment

As a representative of this product you can post one Official Comment on this review. It will appear immediately below the review wherever it is displayed.   Learn more
The following name and badge will be shown with this comment:
 (edit name)
After clicking the Post button you will be asked to create your public name, which will be shown with all your contributions.

Is this your product?

If you are the author, artist, manufacturer or an official representative of this product, you can post an Official Comment on this review. It will appear immediately below the review wherever it is displayed.  Learn more
Otherwise, you can still post a regular comment on this review.

Is this your product?

If you are the author, artist, manufacturer or an official representative of this product, you can post an Official Comment on this review. It will appear immediately below the review wherever it is displayed.   Learn more
System timed out

We were unable to verify whether you represent the product. Please try again later, or retry now. Otherwise you can post a regular comment.

Since you previously posted an Official Comment, this comment will appear in the comment section below. You also have the option to edit your Official Comment.   Learn more
The maximum number of Official Comments have been posted. This comment will appear in the comment section below.   Learn more
Prompts for sign-in

Review Details


5.0 out of 5 stars (2 customer reviews)

4 star

3 star

2 star

1 star

Add to cart Add to wishlist

Location: Pasadena, CA USA

Top Reviewer Ranking: 6,142,848