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.