Physical Sciences and Mathematics 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.

Some Np-Complete Edge Packing And Partitioning Problems In Planar Graphs, Jed Yang

Communications on Number Theory and Combinatorial Theory

Graph packing and partitioning problems have been studied in many contexts, including from the algorithmic complexity perspective. Consider the packing problem of determining whether a graph contains a spanning tree and a cycle that do not share edges. Bernáth and Király proved that this decision problem is NP-complete and asked if the same result holds when restricting to planar graphs. Similarly, they showed that the packing problem with a spanning tree and a path between two distinguished vertices is NP-complete. They also established the NP-completeness of the partitioning problem of determining whether the edge set of a graph can be …

Conflict-Free Vertex Coloring Of Planar Graphs, Shawn Seymour

Scholarly Horizons: University of Minnesota, Morris Undergraduate Journal

The conflict-free coloring problem is a variation of the vertex coloring problem, a classical NP-hard optimization problem. The conflict-free coloring problem aims to color a possibly proper subset of vertices such that there is a unique color within the closed neighborhood (a vertex and its neighbors) of every vertex. This paper presents recent findings and heuristics to solve the conflict-free coloring problem on both general graphs and planar graphs.

A Beautiful Proof By Induction, Lars-Daniel Öhman

Journal of Humanistic Mathematics

The purpose of this note is to present an example of a proof by induction that in the opinion of the present author has great aesthetic value. The proof in question is Thomassen's proof that planar graphs are 5-choosable. I give a self-contained presentation of this result and its proof, and a personal account of why I think this proof is beautiful.

A secondary purpose is to more widely publicize this gem, and hopefully make it part of a standard set of examples for examining characteristics of proofs by induction.