Graph Coloring Problems 1st Edition
Use the Amazon App to scan ISBNs and compare prices.
"Devoted" by Dean Koontz
For the first time in paperback, from Dean Koontz, the master of suspense, comes an epic thriller about a terrifying killer and the singular compassion it will take to defeat him. | Learn more
Enter your mobile number or email address below and we'll send you a link to download the free Kindle App. Then you can start reading Kindle books on your smartphone, tablet, or computer - no Kindle device required.
To get the free app, enter your mobile phone number.
From the Publisher
About the Author
Tommy R. Jensen and Bjarne Toft are the authors of Graph Coloring Problems, published by Wiley.
- Item Weight : 1.08 pounds
- Paperback : 320 pages
- ISBN-10 : 0471028657
- ISBN-13 : 978-0471028659
- Product Dimensions : 5.94 x 0.79 x 9.13 inches
- Publisher : Wiley-Interscience; 1st Edition (December 17, 1994)
- Language: : English
- Best Sellers Rank: #4,938,829 in Books (See Top 100 in Books)
- Customer Reviews:
Top reviews from the United States
There was a problem filtering reviews right now. Please try again later.
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.