Finite H-family distinguishing random graphs

Status open high confidence

Problem 12 from arXiv:2402.04237 asks whether a finite family of graphs $H_1,\dotsc,H_t$ exists such that for almost every $G\in\mathcal{G}(n,\tfrac{1}{2})$, the generalized chromatic polynomials $\pi_G^{(H_i)}$ jointly determine $G$ up to isomorphism. This is posed as a probabilistic weakening of the Bollobás–Pebody–Riordan conjecture (that almost every graph is determined by its chromatic polynomial), in light of the paper's Theorem 5 showing no finite family of generalized chromatic polynomials determines all graphs. No resolution or partial progress on this specific problem was found in the literature as of May 2026.

Reviewer notes. The source paper was published in the Electronic Journal of Combinatorics (2024, v31i4p48). No follow-up paper addressing Problem 12 specifically was found. The conjecture is recent (2024) and the absence of follow-up is consistent with open status at high confidence. The related Bollobás–Pebody–Riordan conjecture (chromatic polynomial determines almost every graph) itself remains open.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).