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:

  1. Assign color 1 to the vertex with highest degree.
  2. Also assign color 1 to any vertex that is not connected to this vertex.
  3. Assign color 2 to the vertex with the next highest degree that is not already colored.
  4. Also assign color 2 to any vertex not connected to this vertex and that is not already colored.
  5. If uncolored vertices remain, assign color 3 to the uncolored vertex with next highest degree and other uncolored, unconnectd vertices.
  6. 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