The counting conjecture for joins of critical graphs and cliques

About 2 years old · traced to

Let GG be a kk-critical graph. For a graph FF, write P(F,r)P(F,r) for the number of proper rr-colorings of FF using the colors 1,…,r1,\ldots,r, and let a rr-fold cover of FF mean a cover in the DP-coloring sense with parameter rr.

Counting conjecture. For all sufficiently large tt and every (k+t)(k+t)-fold cover H\mathcal{H} of G∨KtG\vee K_t, the number of proper H\mathcal{H}-colorings of G∨KtG\vee K_t is at least

P(G∨Kt,k+t).P(G\vee K_t,k+t).

This is presented as an open special case of a broader enumerative question for robustly critical graphs: whether every kk-fold cover has at least as many proper colorings as the chromatic polynomial predicts. The source states that this special case is open, although analogous assertions are known for complete graphs, odd cycles, and joins of odd cycles with cliques.

References

Primary source

Anton Bernshteyn, Hemanshu Kaul, Jeffrey A. Mudrock and Gunjan Sharma, “On strongly and robustly critical graphs”, arXiv:2408.04538 (2026).

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.