CHROMATIC NUMBER OPTIMIZATION FOR EFFICIENT MAP COLORING OF MAHARASHTRA'S DISTRICTS
Megha Abhiman Bhamare · International Journal of Engineering Applied Sciences and Technology · 2024
This research explores the application of graph coloring algorithms to minimize the number of colors required for coloring the districts of Maharashtra, ensuring that no two adjacent districts share the same color. Using an adjacency matrix representation, where each district corresponds to a vertex and edges represent shared borders, the problem is framed as a graph coloring challenge. The primary objective is to demonstrate that a minimum of four colors suffice to color the entire map, in line with the Four Color Theorem, which asserts that any planar map can be colored with at most four colors. A greedy graph coloring algorithm, augmented with backtracking for conflict resolution, is implemented to assign colors to the districts. The results show that the algorithm successfully colors the 36 districts of Maharashtra using no more than four colors, confirming the hypothesis. This research has significant implications for geographical information systems (GIS), political mapping, resource allocation, and optimization problems, offering a practical solution to district-level planning. The methodology and outcomes also suggest potential extensions to other regions and real-world applications, such as task scheduling and frequency assignment in telecommunications.