<![CDATA[Graph coloring is a technique for assigning colors to vertices so that no two adjacent vertices share the same color. This study implements region coloring on the map of North Sulawesi and Gorontalo (Sulut-Go) using the Welch-Powell algorithm, a method based on the highest vertex degree. The research employs a quantitative-descriptive approach with an algorithmic experimental method. Administrative region data and regional boundary connections in the Sulut-Go provinces are converted into graph form, with regencies/cities as vertices and connecting roads as edges. The procedures include data collection, graph construction, degree calculation, coloring using the Welch-Powell algorithm, and chromatic number determination. The results show that the Sulut-Go map consists of 18 regencies/cities represented as vertices. After implementing the Welch-Powell algorithm, the graph coloring produced a chromatic number of χ(G) = 3, meaning all regions can be colored using only three different colors. The coloring was applied with red, yellow, and green, ensuring that no adjacent regions share the same color. Vertex V15 (Minahasa) has the highest degree, with five connections. This study successfully demonstrates that the Welch-Powell algorithm effectively solves the region-coloring problem on the Sulut-Go map. In conclusion, graph coloring using the Welch-Powell algorithm can be effectively applied to color regional maps, facilitating visual distinction between adjacent areas. The chromatic number χ(G) = 3 indicates the minimum number of colors needed for the Sulut-Go map. This research contributes to the application of graph theory in cartography. Further research is recommended for larger-scale applications such as islands or countries, as well as for edge coloring and social network analysis.]]>
