The most important results to analyze are those regarding the reductions in processing time. Many of the results that we received came from equations that showed how much time we theoretically should have saved. There are
2(total number of edges)
total colorings the program would have to analyze if we did not implement our coloring-reduction algorithms to save time. In the case that the number of nodes guessed is 7, there are 21 total edges and 2ˆ21 total colorings or 2,097,152 colorings. Using our first method, the number of total colorings that we need to check is reduced to 2,088,043. The ratio of these different numbers of graphs to test is about 1:1.005 or 200:201. This is a small ratio, but enough to make some difference even though the difference may be quite small.
The second algorithm (alone) reduces the number of colorings to:
2(total number of edges – the number of nodes + 1) x (the number of nodes).
The general ratio is therefore (the number of nodes):
2(the number of nodes - 1).
One can easily notice that the right side will eventually become significantly larger than the left side as we increase the number of edges. Therefore, the larger the n (number of nodes) that we test, the larger the time saving is as a result of the time-saving algorithms. For example, using only the second time reduction algorithm on an R(4, 3) with a guess of 7 nodes, the number of colorings is cut from 2,097,152 to 229,376. The ratio is about 1:9 – a substantial time savings.
However, our results show that the theoretical and actual time savings do not completely coincide. One reason is that our program stops cycling through colorings once it reaches a coloring with no monochromatic subgraphs (this is a result of our previously described use of the “break” operator in Java). Additionally, the two algorithms also overlap in that they would both eliminate some of the same colorings and thus we cannot simply multiply their percent time savings. In addition, especially for the first algorithm, the time to analyze whether the coloring should be tested or not can cut into the expected time savings. Also, many of the beginning graphs contain a node that has only one color coming from it. These colorings have will almost always have a monochromatic subgraph. This is an area for future improvement.