Georgia Institute of Technology College of Sciences

The notion of $S$-labeling, where $S$ is a subset of the symmetric group, is a common generalization of signed $k$-coloring, signed $\mathbb{Z}_k$-coloring, DP (or Correspondence) coloring, group coloring, and coloring of gained graphs that was introduced in 2019 by Jin, Wong, and Zhu.  In this talk we use a well-known theorem of  Alon and F\"{u}redi to present an algebraic technique for bounding the number of colorings of an $S$-labeled graph from below.  While applicable in the broad context of counting colorings of $S$-labeled graphs, we will focus on the case where $S$ is a symmetric group, which corresponds to DP-coloring (or, correspondence coloring) of graphs, and the case where $S$ is a set of linear permutations which is applicable to the coloring of signed graphs, etc.

This technique allows us to prove exponential lower bounds on the number of colorings of any $S$-labeling of graphs that satisfy 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 families of signed (planar) graphs. These lower bounds either improve previously known results, or are first known such results.

This joint work with Samantha Dahlberg and Jeffrey Mudrock.