Discrete Mathematics and Combinatorics Commons^™

Utilizing Graph Thickness Heuristics On The Earth-Moon Problem, Robert C. Weaver

Rose-Hulman Undergraduate Mathematics Journal

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.