The counting conjecture for joins of critical graphs and cliques
The counting conjecture for joins of critical graphs and cliques
Let be a -critical graph. For a graph , write for the number of proper -colorings of using the colors , and let a -fold cover of mean a cover in the DP-coloring sense with parameter .
Counting conjecture. For all sufficiently large and every -fold cover of , the number of proper -colorings of is at least
This is presented as an open special case of a broader enumerative question for robustly critical graphs: whether every -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
Sign in to submit a solution.
No solutions have been posted yet.