Comparative Analysis of Graph Coloring Algorithms

Overview

Many real-world issues such as coloring geographical maps and scheduling, can correspond to one of graph theory’s most important concepts: graph coloring problems. As the complexity of these real-world issues increases, the corresponding graphs increase in size, thus making them impossible to color manually. In this project, a graph coloring program with a focus on map coloring problems has been developed using the programming language Python. The aim was to minimize both the number of colors used, and the time taken to color the graph. The main goal was to find a good balance between the two. The program compares three algorithms: the brute force algorithm, the greedy algorithm, and the backtracking recursive algorithm. Using the program, the greedy algorithm has been modified to sort the sequence of vertices by degree. The performance of each algorithm was tested on graphs with densities 20%, 50% and 80%. It has been concluded that the greedy algorithm sorted in descending order uses fewer colors than in ascending order. As for time comparison, the greedy algorithm proved to be the fastest, followed by the backtracking recursive algorithm, then the brute force algorithm. Finally, the backtracking recursive algorithm, limited to a palette size of four, was selected for map coloring problems. This program can be applied as a serious game that teaches users graph theory, graph coloring, and its related computing concepts and algorithms.

Competition history

• ISEF 2017 Systems Software · Entry SOFT048

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.