Theoretical and Natural Science
- The Open Access Proceedings Series for Conferences
Theoretical and Natural Science
Vol. 28, 26 December 2023
Open
Access | Article
Optimizing map coloring: Using linear programming to find the minimum number of colors
* Author to whom correspondence should be addressed.
Abstract
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.
Keywords
linear programming, map coloring, optimization, constraints, modeling
References
1. Gardner, M. (1975). Mathematical Games: The Four-Color Problem. Scientific American, 232(4), 112-117.
2. Appel, K. and Haken, W. (1977) Every Planar Map Is Four Colorable. Part I discharging. Illinoi-s Journal of Mathematics, 21, 429-490. - references - scientific research publishing. (n.d.). R-etrieved March 6, 2023, from Scirp.org website: https://www.scirp.org/(S(lz5mqp453edsnp5-5rrgjct55))/reference/referencespapers.aspx?referenceid=1929762.
3. Gerard Sierksma; Yori Zwols (2015). Linear and Integer Optimization: Theory and Practice (3rd ed.). CRC Press. p. 1. ISBN 978-1498710169.
4. Kaufmann, M., & Wiese, R. (1997). Simulated annealing for coloring random graphs. Journal of Statistical Physics, 87(5–6), 1207–1225. doi:10.1007/BF02181453.
5. Pincus, Martin (Nov–Dec 1970). "A Monte-Carlo Method for the Approximate Solution of Certain Types of Constrained Optimization Problems". Journal of the Operations Research Society of America. 18 (6): 967–1235. doi:10.1287/opre.18.6.1225.
6. Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 19. ISBN 978-0-486-67870-2. Archived from the original on 5 May 2019. Retrieved 8 August 2012. A graph is an object consisting of two sets called its vertex set and its edge set.
7. Wikipedia contributors. (2023, February 11). Adjacency matrix. Retrieved from Wikipedia, The Free Encyclopedia website: https://en.wikipedia.org/w/index.php?title=Adjacency_matrix&oldid=1138782609.
8. Wikipedia contributors. (2023b, February 18). Henan. Retrieved from Wikipedia, The Free Enc-yclopedia website: https://en.wikipedia.org/w/index.php?title=Henan&oldid=1140159930.
9. Barnette, D. (1983). Map Coloring, Polyhedra, and the Four-Color Problem. Providence, RI: Mathematical Association of America.
10. Wikipedia contributors. (2023d, March 2). List of optimization software. Retrieved from Wikipe-dia, The Free Encyclopedia website: https://en.wikipedia.org/w/index.php?title=List_of_opt-imization_software&oldid=1142468626.
Data Availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. Authors who publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See Open Access Instruction).
- Volume Title
- Proceedings of the 2023 International Conference on Mathematical Physics and Computational Simulation
- ISBN (Print)
- 978-1-83558-261-9
- ISBN (Online)
- 978-1-83558-262-6
- Published Date
- 26 December 2023
- Series
- Theoretical and Natural Science
- ISSN (Print)
- 2753-8818
- ISSN (Online)
- 2753-8826
- DOI
- 10.54254/2753-8818/28/20230312
- Copyright
- 26 December 2023
- Open Access
- This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited