The linear color function equals the DP color function for prime powers
The linear color function equals the DP color function for prime powers
Let be a power of a prime. For a graph , let be the minimum number of colorings over all -labelings, where is the collection of -linear permutations of , and let denote the DP color function. The linear-color-function conjecture. For every graph ,
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 fails for the DP color function; the source states that it is open for prime powers and true for .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.