Tuesday, July 2 2019
10:00am - 12:00pm
PhD Thesis Presentation
Computational Methods for Graph Choosability and Applications to List Coloring Problems

A subcubic planar graph is a graph such that every vertex has degree at most three and which can be embedded in the plane without any edge crossings. The square of a graph G is the graph obtained from G by adding edges between pairs of vertices which have distance 2 in G. Wegner (1977) conjectured that the square of any subcubic planar graph has chromatic number at most 7, and Cranston and Kim (2008) asked if this conjecture could be extended to list coloring. We prove this stronger result, that the square of any subcubic planar graph has list-chromatic number at most 7. (In other words, all planar graphs are 7-square-choosable.) Our proof uses the discharging method and analyzes the choosability of many small subgraphs for our list of reducible configurations. However, graph choosability is a Pi^2-complete problem (which is higher than NP-complete in the polynomial complexity hierarchy). To successfully verify this list of reducible configurations, we develop and apply new computational methods.
Speaker:Luke Nelsen
Affiliation:
Location:4113


Download as iCalendar

Done