Algorithms

Here is an algorithm for graph coloring from the book,
Discrete Mathematics and its Applications,
by Kennth H. Rosen:

- Assign
**color 1**to the vertex with highest degree. - Also assign
**color 1**to any vertex that is not connected to this vertex. - Assign
**color 2**to the vertex with the next highest degree that is not already colored. - Also assign
**color 2**to any vertex not connected to this vertex and that is not already colored. - If uncolored vertices remain, assign
**color 3**to the uncolored vertex with next highest degree and other uncolored, unconnectd vertices. - Proceed in this manner until all vertices are colored.

Try this algorithm with the graph of South America. Did you find the same chromatic number as you did the first time you colored it without the aid of an algorithm?

Next: Edge Coloring

Back: Algorithms