The counting conjecture for joins of critical graphs and cliques

From papers

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 GKtG\vee K_t, the number of proper H\mathcal{H}-colorings of GKtG\vee K_t is at least

P(GKt,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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.