My name is David Lapayowker, and I'm working with Dr. Dan Cranston on the Efficient Graph Coloring project. For a concise description of what graph coloring means, Wikipedia has a rather good article here. Graph coloring has numerous useful applications in a number of fields, most notably in areas like scheduling and allocation. However, like many other useful problems, even being able to determine if a graph can be colored with a certain number of colors is NP-Complete. In layman's terms, this means that trying to color a graph efficiently is intractably difficult for an arbitrary graph, and it's extremely unlikely that we're ever going to find an efficient way of doing it.

However, this is not to say that we can never efficiently find the number of colors needed to color a graph. In particular, by knowing something about the structure of a graph, we may be able to narrow down the number of colors needed, sometimes dramatically. For instance, the 4 Color Theorem states that for a planar graph, the maximum number of colors required to color the graph will always be four, no matter what. The goal of this project is to look into other graph structures to see if we can find other such cases where we can find useful upper or lower bounds on the number of colors, or the exact number of colors needed.

More specifically, we want to look at the total list coloring of planar graphs. A total coloring is similar to a vertex coloring, except we wish to give every vertex, edge and face a color, so that no elements that meet anywhere share a color. List coloring is slightly more complicated, and anyone who wants clarification about what it means can feel free to email me and I'd be happy to give clarification. It is conjectured that all planar graphs can be list colored with lists of size equal to the highest degree in the graph, plus 4. There is a similar result known for total coloring (i.e. not using lists) for planar graphs of a particular size, but it is unknown if this extends to list coloring. The goal of my project is to find out if any similar arguments can be made.

Those interested in seeing my final presentation can find it here.