Abstract
The question of Graph Isomorphism's (GI) true time complexity classification has remained a mystery for years. It is certainly in NP but uncertain whether or not it is in P, with many suggesting it is in fact NP-Intermediate. Despite many special case polytime solvers existing, a recent breakthrough in the field has only improved the problem's time complexity to "quasi-polytime" $O(n^{log^cn})$. This thesis proposes an "over-coloring" approach to canonical label construction that is $O(n^4)$ and offers reasoning and empirical evidence that suggest it is a bijective (1:1) map from graph symmetric groups to canonical labels. That is to say, the proposed function overColor(G) takes as input a graph G and outputs a canonical label for G: a label that is unique to only G and the set of all graphs isomorphic to G. Then, three comparison algorithms that can each be used to distinguish the labels in polytime, polytime, and factorial time respectively are provided. The first algorithm used for comparison is a valid polytime GI solver if and only if the function overColor(G) is invertible (1:1). The second allows for a naïve reconstruction of the permutation between input graphs. The third offers a true reconstruction of this permutation matrix that leverages canonical labels to prune the permutation search space. A conjecture for the reduction of polytime GI to the invertibility of overColor(G) is offered and future work is discussed for how this conjecture can be used to aid in solving polytime GI itself. Lastly, supporting experimental evidence for both random graphs and specific k-regular and Johnson graphs is offered to demonstrate overColor(G)'s robustness in these spaces that suggests it may be 1:1.