Friday, April 22 2022
11:30am - 1:00pm
PhD Thesis Presentation
Computational Methods Applied to Graph Coloring Problems

The discharging method is a common technique applied to coloring problems on planar graphs. We discuss the main ideas of the discharging method and apply it to the square choosability number of planar graphs. A generalization of the usual vertex coloring, the square choosability number is the least size of lists of colors needed to be assigned to the vertices of a graph so that, no matter what colors are in the lists, every vertex can be colored with a color from its list and every two vertices at distance at most two from each other receive different colors. A key component of our approach is the use of computers to handle the complexity of parts of the proof.

We also discuss computational methods to automatically generate discharging arguments for coloring problems. This is achievable by viewing a discharging argument as a linear program and applying linear programming methods, such as cut and column generation. We also present a family of graphs with Alon-Tarsi number arbitrarily larger than the correspondence chromatic number, and another family of graphs with correspondence chromatic number larger than the Alon-Tarsi number. We also discuss odd covers of graphs, a collection of complete bipartite graphs, or bicliques, whose symmetric difference is the original graph. We show a lower bound on the minimum size of an odd cover and some graphs for which that bound is tight or almost tight.
Speaker:Eric Culver
Location:Zoom - check email

Download as iCalendar