Speaker: Hemanshu Kaul (Illinois Institute of Technology)
Title: A Polynomial Method for Counting Colorings of S-labeled Graphs
Abstract: The notion of S-labeling, where S is a subset of the symmetric group, is a common generalization of signed k-coloring, signed Z_k-coloring, DP-coloring, group coloring, and coloring of gained graphs that was introduced in 2019 by Jin, Wong, and Zhu. In this paper, we present a unified and simple polynomial method for giving exponential lower bounds on the number of colorings of an S-labeled graph. This algebraic technique allows us to prove exponential lower bounds on the number of colorings of any S-labeling of graphs satisfying certain sparsity conditions. We apply these to give exponential lower bounds on the number of DP-colorings (and consequently, number of list colorings, or usual colorings) of families of planar graphs, and on the number of colorings of signed graphs. These lower bounds either improve previously known results, or are first known such results.
This is joint work with Samantha Dahlberg and Jeffrey Mudrock.
