Graph Colouring Algorithm

This algorithm has two main parts: building a spanning tree and resolving any edges which do not make it into the tree. We choose colors as we go, as described below.

We assume an undirected, connected graph with no self-referencing edges.

Building A Spanning Tree
Resolving Conflict
Demonstration

Building A Spanning Tree

To build a spanning tree, we pick some arbitrary vertex and colour it red. Then, for each edge, we look at the vertex on the other end. If it is not coloured, we colour it green and call ourselves recursively on that green vertex, swapping our primary colour (red) and secondary colour (green). If the vertex is already coloured, however, we add that edge to a queue of conflicted edges and try another edge which connects to our red vertex. When we have finished with all edges, return. The end result is a spanning tree, formed in a depth-first manner, which is 2-coloured. We also have a queue of conflicting edges.

	v = get_arbitrary_vertex(G)
	conflicted_edges = []
	build_span(G, v, red, green, conflicted_edges)

        [...resolve conflicts, see below...]
	colours = [red, green]
	resolve_conflicts(G, conflicted_edges, colours)

        exit

        sub build_span(graph, vertex, colour1, colour2, conflicts)
		colour_vertex(vertex, colour1)
		foreach edge e in G
			w = destination(G, vertex, e)
			if is_colored(w) 
				queue(e, conflicts)
			else
				build_span(graph, w, colour2, colour1, conflicts)
		[...no more edges...]
		return

Resolving Conflicts

Each edge in our queue represents a possible colouring conflict. For each edge, the vertices involved are named v and w in the following manner:

If one vertex has more conflicted edges connecting to it, that vertex is v
Else, if one vertex has a higher degree than the other, that vertex is v
Else, pick a v arbitrarily

We choose v and w in this manner as a heuristic. The goal is to have v be the vertex which would derive more benefit from having a unique colour; if we must create a new colour, it will be given to v.

First, make sure that v and w are the same colour. They might not be! Consider the result of the spanning tree algorithm on a square: you end up with a "U" shape, and the 1 conflicted edge is between a red vertex and a green vertex. If they are not the same colour, we can consider this edge resolved and move on.

If v and w are the same colour, we need to resolve a conflict. Considering all edges of v (not just conflicted or nonconflicted edges), see if there's some colour we've already used with which v does not conflict. If such a colour exists, colour v that colour. The edge is now resolved.
If we find no such colour for v, try to find one for w. If we succeed, colour w that colour. The edge is now resolved.
Well, if we can't find an existing colour for v or w, we need to make a new colour. Give this colour to v, and add the new colour to a list of colours. The edge is now resolved.

Continue to use this resolving technique on all conflicted edges. When you have completed, the graph is correctly coloured (though perhaps not minimally).
This algorithm will inherently result in a coloring <= maxdegree(G) + 1.
This algorithm will also inherently result in a coloring >= maxclique(G). =)

	sub resolve_conflicts(graph, edges, colours)
		for each edge e in edges
			(v, w) = rank_vertices(graph, e)
			if colour(v) != colour(w)
				continue

			col = get_unconflicted_colour(G, v, colours)
			if(col)
				colour_vertex(v, col)
				continue

			col = get_unconflicted_colour(G, w, colours)
			if(vol)
				colour_vertex(w, col)
				continue

			col = make_new_colour(colours)
			colour_vertex(v, col)

			[...add to our list of colours...]
			colours = [colours, col]

Demonstration

The below pages step through an example of this algorithm being applied to a graph. The demonstration is for the most part step by step.

There's two ways to go about looking at the graphs: either one at a time (each page links to the next), or all at once. Each .png is 5-7k or so, and total somewhere in the area of 150k.

Note: Netscape 4.x does not seem capable of correctly rendering these pngs. =(
Mozilla handles them fine, however.

graph 01 graph 02 graph 03 graph 04 graph 05 graph 06 graph 07 graph 08 graph 09 graph 10 graph 11 graph 12 graph 13 graph 14 graph 15 graph 16 graph 17 graph 18 graph 19 graph 20 graph 21 graph 22 graph 23 graph 24 graph 25

All in one