Implementing Welsh-Powell Algorithm on Coloring the Map of West Java

Graph Theory is a very complex and difficult mathematical problem, with Graph Coloring as one of its most studied problem. Graph Coloring itself is an implementation of Graph Theory, where there can’t be neighboring vertexes that share the same color. At the same time, the aim of Graph Coloring is to have the least color used (Chromatic Number) to color the vertexes in a graph, while there can’t be any neighboring vertexes that have the same color. In this paper, we’re experimenting on one of the Graph Coloring implementations, which is Map Coloring. We’re experimenting on the usage of Welsh-Powell Algorithm, an algorithm deemed suitable for Scheduling, another implementation of Graph Coloring, and see if this algorithm is also suitable and usable for Map Coloring. By using the map of West Java as our dataset and converting it to a graph and then to a matrix, we obtained a result in the shape of a colored map. Our result proves that Welsh-Powell algorithm is indeed suitable and usable, providing a satisfactory output where it’s uncomplicated to observe and the limits of areas (districts and cities) are clearly visible. In addition to that, Welsh-Powell Algorithm managed to perform better than the Greedy Algorithm from similar research, resulting a map with the same Chromatic Number as a map with lesser vertices colored by the Greedy Algorithm.