DKE Project 1: A challenge for optimal graph colorings. A graph is a set of vertices that may be connected by one or more edges to other vertices in the graph. In this project, all edges in all graphs are bi-directional. Graph coloring is an NP-hard problem, meaning in layman's terms that the optimal coloring is computationally difficult, and scales exponentially as the size of the graph grows. This project addressed the graph coloring problem by attempting to find the best lower and upper bound estimates, and if these two estimates were identical, then we know we have found an optimal graph coloring/the chromatic number. The chromatic number is the fewest amount of colors required to properly color a given graph.
This project reads in a graph in the form of a .csv file, and displays them either visually in the GUI, or can be run via CLI.
Algorithms used include Welsh-Powell (lower bounds), Max Clique (lower bounds), DSATUR (upper bounds), Recursive Largest-First (upper bounds), a heuristic Greedy algorithm, and a brute force algorithm.
Instructions on how to run this program will be included in the future.
Please see "Project Report" for the final report PDF with our analysis of our program.