Discrete Applied Math Seminar by Gunjan Sharma: "Shameful" and Related Inequalities for List and DP Colorings of Graphs

Speaker:

Gunjan Sharma, Illinois Institute of Technology

Title:

"Shameful" and Related Inequalities for List and DP Colorings of Graphs

Abstract:

For an n-vertex graph G, we define the mean color number of G to be the average number of colors used to properly color G using a palette of n colors. It is easy to see that the mean color number is maximized when G is a complete graph. In 1995, Bartels and Welsh conjectured that over all n-vertex graphs, the empty graph has the smallest mean color number. This seems intuitively obvious but it could not be proved at the time. So Bartels and Welsh named it the shameful conjecture. A stronger version of it was proved by Dong five year later which can be interpreted as follows. Let k ≥ n − 1. Suppose each vertex in G is colored with one of the k colors uniformly and independently. Then the probability that a uniformly chosen random (k + 1)-coloring is a proper coloring of G is at least as much as the probability that a uniformly chosen random k-coloring of G is proper. We call this inequality the shameful inequality. The shameful inequality does not hold for all values of k even though it feels quite intuitive that must be true in general.

Motivated by this, we are interested in studying the list, the DP and the dual DP analogues of the shameful inequality for any graph. In particular, we show that both the list and the DP analogues of the shameful inequality are true for all values of k. For the dual DP color function, we give a lower bound on k when the shameful inequality analogue holds. Furthermore, we show that just like in the case of the chromatic polynomial, the dual DP analogue of the shameful inequality does not hold for all values of k. For a given graph, we also give asymptotic bounds on the difference between the chromatic polynomial and the DP color function, as well as the difference between the dual DP color function and the chromatic polynomial, in terms of the cycle structure of the graph.

This is joint work with Hemanshu Kaul and Jeffery Mudrock.

Discrete Applied Math Seminar

Request Zoom Link