The linear color function equals the DP color function for prime powers

Let kk be a power of a prime. For a graph GG, let PLk(G,k)P_{\mathcal{L}_k}(G,k) be the minimum number of colorings over all Lk\mathcal{L}_k-labelings, where Lk\mathcal{L}_k is the collection of Fk\mathbb{F}_k-linear permutations of Fk\mathbb{F}_k, and let PDP(G,k)P_{DP}(G,k) denote the DP color function. The linear-color-function conjecture. For every graph GG,

PLk(G,k)=PDP(G,k).P_{\mathcal{L}_k}(G,k)=P_{DP}(G,k).

The conjecture would identify the restricted linear-labeling model with the general DP-coloring model for prime-power numbers of colors. It is motivated by the fact that the authors know of no graph for which the lower bound obtained for PLk(G,k)P_{\mathcal{L}_k}(G,k) fails for the DP color function; the source states that it is open for prime powers k4k\geq 4 and true for k=2,3k=2,3.

Sources & referencesView supporting material

Primary source

Samantha L. Dahlberg, Hemanshu Kaul and Jeffrey A. Mudrock, “A Polynomial Method for Counting Colorings of Sparse Graphs”, arXiv:2312.11744 (2024).

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.