Dual-DP Shameful inequality conjecture

Let GG be a graph on nn vertices, and let PDP(G,k)P^{*}_{DP}(G,k) denote its dual DP color function, the maximum number of colorings over all full kk-fold covers of GG. Dual-DP Shameful inequality conjecture. For every nn-vertex graph GG and every kNk\in\mathbb{N} satisfying kn1k\geq n-1,

PDP(G,k+1)(k+1)nPDP(G,k)kn.\frac{P^{*}_{DP}(G,k+1)}{(k+1)^n}\geq\frac{P^{*}_{DP}(G,k)}{k^n}.

The text motivates this as an expected extension of the Shameful inequality: it notes counterexamples for smaller values of kk, while giving no resolution of the stated range, so the conjecture is open.

Sources & referencesView supporting material

Primary source

Hemanshu Kaul, Jeffrey A. Mudrock and Gunjan Sharma, “Shameful Inequalities for List and DP Coloring of Graphs”, arXiv:2412.16790 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.