 |
|
 |
|
|
|
|
Introduction: Graph coloring is a subject that has numerous applications in operations research and computer science. We will consider the basics and consider some of the applications.
1. The Four-Color Theorem has been around for years, but only relatively recently (1976) was it proved, and that with the aid of a computer. Since no human has yet looked at every section of the proof, has the theorem really been proved? (N. Robertson, D. P. Sanders, P. D. Seymour and R. Thomas independently developed another different computer proof in 1997. See http://www.math.gatech.edu/~thomas/FC/fourcolor.html for some history as well as information on the new proof. Does this make the proof more acceptable to you?)
2. The author sneaks two important rules for k-coloring in on us on p. 73 in the paragraph just above Example 2. One concerns complete subgraphs and the other concerns vertices of degree < k in a k-coloring. Be sure that you notice them them.
3. The examples give several interesting applications of graph coloring applications. You should make sure you read them carefully and understand them.