13 of 13 people found the following review helpful
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 mediumsized 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 TheoremProof 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 WellOrdering Theorem of set theory... However, even if it is not assumed that every set has a wellordering, 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 wellordering 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 fourcolor theorem...?", "Is there a short argument to demonstrate that the fourcolor 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 4colorable?", 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 "listchromatic 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 online archive for uptotheminute 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?
Graph Coloring Problems 0471028657
Tommy R. Jensen
WileyInterscience
Graph Coloring Problems
Books
A concise catalog of theorems and conjectures.
This is a highly technical book that gathers together in one mediumsized 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 TheoremProof 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 WellOrdering Theorem of set theory... However, even if it is not assumed that every set has a wellordering, 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 wellordering 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 fourcolor theorem...?", "Is there a short argument to demonstrate that the fourcolor 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 4colorable?", 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 "listchromatic 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 online archive for uptotheminute 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.
James Arvo
July 14, 2003
 Overall: 5

Review Details
Location: Pasadena, CA USA
Top Reviewer Ranking: 4,121,586
