Utilizing graph thickness heuristics on the Earth-moon Problem

Authors

Robert C. Weaver, York College of PennsylvaniaFollow

Abstract

This paper utilizes heuristic algorithms for determining graph thickness in order to attempt to find a 10-chromatic thickness-2 graph. Doing so would eliminate 9 colors as a potential solution to the Earth-moon Problem. An empirical analysis of the algorithms made by the author are provided. Additionally, the paper lists various graphs that may or nearly have a thickness of 2, which may be solutions if one can find two planar subgraphs that partition all of the graph’s edges.

Author Bio

Robert Weaver is a ‘23 Mathematics student with a Computer Science minor at York College of Pennsylvania. After discovering his interests in graph theory and computer science, Robert pursued a research project that would allow him to delve into both of these topics. Currently, Robert works as a Software Engineer at Johnson Controls and plans to return to the university setting to acquire a Master’s degree in Computer Science.

Faculty Sponsor

Frederick Butler

Recommended Citation

Weaver, Robert C. (2023) "Utilizing graph thickness heuristics on the Earth-moon Problem," Rose-Hulman Undergraduate Mathematics Journal: Vol. 24: Iss. 2, Article 5.
Available at: https://scholar.rose-hulman.edu/rhumj/vol24/iss2/5