Discrete Applied Mathematics Seminar by Gunjan Sharma: Shameful Inequalities for List and DP Coloring of Graphs

Speaker: Gunjan Sharma, visiting assistant professor of mathematics and computer science, Lake Forest College

Title: Shameful Inequalities for List and DP Coloring of Graphs

Abstract:

The chromatic polynomial \(P(G,k)\), introduced by Birkhoff in 1912, counts the number of proper \(k\)-colorings of a graph \(G\). Enumerative analogues have since been developed for two generalizations of graph coloring: list coloring, via the list color function \(P_{\ell}\), and DP-coloring, via the DP color function \(P_{DP}\) and the dual DP color function \(P^*_{DP}\). For any graph \(G\) and \(k\in\mathbb{N}\), these functions satisfy \(P_{DP}(G,k)\le P_{\ell}(G,k)\le P(G,k)\le P^*_{DP}(G,k)\). In 2000, Dong settled the so-called Shameful Conjecture of Bartels and Welsh by proving that for any \(n\)-vertex graph \(G\), \(\frac{P(G,k+1)}{(k+1)^n}\ge \frac{P(G,k)}{k^n}\) for all \(k\ge n-1\), while Seymour showed that the inequality can fail for smaller \(k\). We study analogous inequalities for list and DP color functions. We prove that for any \(n\)-vertex graph \(G\), \(\frac{P_{\ell}(G,k+1)}{(k+1)^n}\ge \frac{P_{\ell}(G,k)}{k^n}\) and \(\frac{P_{DP}(G,k+1)}{(k+1)^n}\ge \frac{P_{DP}(G,k)}{k^n}\) for all \(k\in\mathbb{N}\). For the dual DP color function, we show that the inequality fails in general but holds for all \(k\ge n-1\) when \(G\) is an \(n\)-vertex complete bipartite graph.

This is joint work with Hemanshu Kaul and Jeffrey Mudrock.

Discrete Applied Math seminar