Nonexistence of almost-complete Harary polynomials
Nonexistence of almost-complete Harary polynomials
Let be the random graph model with edge probability , and let a Harary polynomial be a graph polynomial arising from a graph property. A graph polynomial is almost complete when asymptotically almost all graphs in the model are uniquely determined by it.
Harary almost-completeness conjecture. There is no Harary polynomial which is almost complete for .
This is proposed in contrast with the Bollobás–Pebody–Riordan conjecture for the chromatic polynomial. The supplied text gives no resolution or supporting theorem for this stronger nonexistence claim.
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
Johann A. Makowsky, “Distinctive power and comparability of Harary polynomial”, arXiv:2512.22556 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.