Map coloring is a classic problem in graph theory and it relates to many optimization techniques in mathematics such as linear programming and simulated annealing. This paper investigates the minimum number of colors required to color a map under different constraints and situations using linear programming. Specifically, it examines three different scenarios: (1) coloring each district on the map with the constraint that adjacent districts must be colored differently, (2) adding the additional constraint that two regions bordering the same region cannot be colored the same, and (3) assigning two colors to each district with the constraint that adjacent districts must be colored differently. To proceed with the research, hypotheses are formulated regarding the impact of these additional constraints on the minimum number of colors required to color the map. The data in the paper is collected by creating sample maps and analyzing the minimum number of colors required to color them under each of the different scenarios. The findings of this research suggest that the addition of constraints, indicating a complex situation, increases the minimum number of colors needed to color the map. Thus, linear programming is found to be an effective optimization technique for solving map coloring problems under these constraints. This research makes a valuable contribution to the field of mathematics and computer science, providing insights into the application of optimization techniques to real-world problems like map coloring. The findings of the research have significant implications for practitioners working in the field of optimization and inform the development of more efficient algorithms for solving map coloring problems.
Research Article
Open Access