Implementation of Graph Coloring on the Map of North Gorontalo District Using the D’Satur Algorithm and the Backtracking Algorithm

Graph Coloring is the process of assigning colors to vertices such that no adjacent vertices share the same color, using the minimal number of colors possible. This study aims to implement graph coloring to the map of North Gorontalo Regency, which consists of 11 sub-districts and 123 villages, utilizing the D’Satur and Backtracking algorithms. It also compares the algorithms in terms of the smallest chromatic number and identifies strategic points in North Gorontalo Regency, particularly in sub-districts, based on the number of adjacent vertices. The study employed a case study method to gather information, specifically the map of North Gorontalo Regency. The results demonstrate that graph coloring of the map utilizing the D’Satur algorithm produces a chromatic number of (χ = 3) for sub-districts and (χ = 5) for villages. Meanwhile, the Backtracking algorithm yields a chromatic number of (χ = 3) for districts and (χ = 4) for villages. Thus, for sub-district coloring, both algorithms yield the same chromatic number. However, the Backtracking algorithm performs better for village coloring, as it produces the smallest chromatic number. The identified strategic sub-district is Kwandang, which has the highest degree of 4.