E -X -T -E -N - D your Knowledge:
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
Next: Edge Coloring