When initially looking at this problem, I was considering all types of graphs as valid members of my potential data set. The problem here is that most graphs are not three-colorable. In this way, I would find myself looking for extremely rare cases in an infinitely large data set. I chose to limit my set of graphs to only planar graphs in the hope that I would be more likely to find three-colorings among this subclass. Planar graphs are more restricted in their design than non-planar graphs and therefore have a higher probability of being three-colorable. For example a K₄ configuration (a complete graph on 4 vertices) within any graph will make it non-three-colorable. A planar graph may not have a K₅ configuration within it and therefore will also have no configuration of K_j where j is greater than 5. (Any complete graph is a subgraph of a complete graph on a larger number of vertices). This greatly increases the likelihood of finding three-colorable graphs within this subset.

To attempt to solve this problem on a grid, I first needed to design a method of breaking it into smaller pieces that could be computed at the same time. To do this, I first needed to implement a serial algorithm to three-color graphs. I chose to make this algorithm as general as possible, rather than use various tricks to affect the speed. This basic algorithm took this simple form:

• Generate all possible colorings for a graph using three colors.
• Test each of these colorings to see if it was a properly three-colored graph.

The time of this algorithm was O(n³). In fact, this was not just the worst-case time, but also the exact time for any graph with n vertices. I chose not to use any speedup tricks (such as skipping trivially incorrectly colored graphs of all vertices having the same color) so that I could get actual speed estimates. With exponential time algorithms, tricks like this decrease in effectiveness as the size of the problem increases to the point where their effect in negligible.

This initial algorithm was written recursively, as this was the easiest method. It has been shown that any recursive algorithm can be written in an iterative form and this was the first method of parallelization that I considered. With an iterative algorithm, I could simply run a subset of the iterations on each agent and return a final result. This would have taken the form of distributing n³/p colorings to each agent and having them each return the proper three-colorings to the controller. While this would guarantee a time complexity of O(n³/p), it would not go any further.

The algorithm I used took a specific approach to graph coloring as opposed to using the general method for parallelizing search.

• Break the graph into subgraphs
• For each subgraph
• Generate all possible colorings for a graph using three colors.
• Test each of these colorings to see if it was a properly three-colored graph.
• Recombine the subgraphs two at a time by putting both sets of vertices in one graph and validating three-coloring compatibility

Breaking the graphs into subgraphs was the easiest. My particular test graphs tended to be labeled with vertex numbers relative to their position. Therefore, so as not to lose any generality, I made the distribution of vertices evenly spread over the entire set of vertices. The breaking algorithm does not need to be parallelized as it takes O(n) time. This is quite fast when compared to the other parts of the algorithm.

Coloring and checking each subgraph takes the same time as in the basic algorithm, except it now runs on much smaller graphs. We can see that the time per subgraph will be: T_S = 3^n/k where k is the number of subgraphs, and n is the number of vertices. This leads us to the total time for this phase T = (k/p)•T_S. This time is on the order of O(3ⁿ/(p•k)).

The recombination of the graphs is problematic in that it is a multi-step problem. The algorithm for recombining two graphs, A and B, is relatively simple: place the set of all vertices from A and from B into a new graph, then validate all combinations of each graph’s three-colorings with the other’s, finally set the three-colorings of the new graph to any combinations of three-colorings that passed the validation test. The time to combine two subgraphs will be dependant on an unknown function S(j) which is the average number of three-colorings for a planar graph of size j. T = C(s)² where s is the size of the subgraphs (s=n/k).

Because recombination is a multi-step problem we will need to perform this recombination 2^(k-1)/2 times based on a tree structure. This shows that the total time spent in this part of the algorithm is T•2^(k-1)/2. This is proportional to O(2^k). We can now see that the total time of the first and second phases can be added.

The total run time of this operation is largely dependent on k, n, and p. While n and p are considered fixed for each run, the value to k can be changed to optimize the time. A large value for k would focus more time on the recombination step whereas a small k-value would force longer times on the coloring step and require fewer recombination operations.