Introduction

Contains some initial work on edge colorings for detour length paths. Thus far, we successfully check for -color connectivity, determine minimum detour numbers, and view chord additions as permutations of distance between chord incident vertices. Thus far, and algorithmic approach to minimally -color connecting a graph has not been implemented, and the proposed solution cannot be determined to halt unless the -color connection number of any graph is less than .

A number of intractable problems arise as we begin exploring this topic. Rainbow-connection numbers (Li, Sun 2012) have been determined to be NP-Hard, likewise the computation of detour matrices has no efficient algorithm; the problem of -color connecting a graph relies on both rainbow-connections, and minimum detour numbers. Regarding the programs, the wolfram package makes use of a graph isomorphism module which separates chorded cycles into equivalence classes; this is done using a function map, making it ideal for usage in parallel. The python files generate a set of all chorded cycles and separate them into classes by there detour number.

An approximation of the -color connection number can be generated using DetourModule.wl, although that package has bugs. It uses all paths of length or greater to color the graph, depending on how frequently a particular edge occurs in a length path.

Interesting Visualizations

While technically out of the scope of the project, I explored some different avenues that led to some interesting images. It became clear that while two chords were responsible for increased detour number of a graph, only certain combinations of these chords would work. We define a new graph, where edges become vertices, and these vertices are adjacent if their presence in the original graph results in a path of length . While the graphs themselves didn't illustrate much, we can see patterns emerge from the adjacency matrices.

where	where	where