Dual-DP Shameful inequality conjecture

About 2 years old · traced to

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 k∈Nk\in\mathbb{N} satisfying k≥n−1k\geq n-1,

PDP∗(G,k+1)(k+1)n≥PDP∗(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.

References

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.