 |
|
 |
|
|
|
|
Introduction: In this section we consider some theorems to help us with the subject of finding the chromatic number of graphs. Coloring theory has been around for over a century and so has been well developed. Here we meet some of the basic results.
|
|
1. Even though we will not prove all the theorems in this section, you should make sure that you understand what they say and how to use them. Some are pretty obvious, but some are not.
2. The proof of Theorem 5 is along the same lines as the first (false) proof of the Four-Color Theorem. Even though it fails to work in that case, it does work for Theorem 5, and you should be sure that you can follow the reasoning.
3. We will go into more depth on the Chromatic Polynomials introduced in the previous section. Take a look at Bondy & Murty p. 125 Their entire out-of-print text, Graph Theory with Applications, is available on-line and is also on the S-drive.