H-coloring graph polynomial determination
Problem 11 · arXiv:2402.04237
Status open high confidence
Problem 11 asks for which graphs $H$ there exists $H'$ such that $\pi_G^{(H')}$ determines $\pi_G^{(H)}$ for every graph $G$; it remains open. The motivating special case — Conjecture 5.2 of Asgarli, Krehbiel, Levinson, and Russell (arXiv:2401.12883), that $\pi_G^{(K_2)}$ determines the chromatic polynomial $\pi_G^{(K_1)}$ — is itself still unresolved as of the source paper. No post-2024 follow-up resolving the general problem was found in the indexed literature.
Reviewer notes. The Asgarli et al. paper arXiv:2401.12883 (published in Graphs and Combinatorics, 2025) is the source of Conjecture 5.2 that motivates Problem 11; it predates 2402.04237 and so is not a since_posted entry. Remark 10 of the source paper shows that for any connected H, a finite family (not a single H') suffices to determine pi_G^(H), making Problem 11's single-graph H' requirement the non-trivial constraint. No paper resolving or significantly advancing Problem 11 was found within the 5-call cap.
Context
Asgarli et al. conjectured (their Conjecture 5.2) that $\pi_{G}^{(K_{2})}$ determines the chromatic polynomial $\pi_{G}^{(K_{1})}$, i.e., that equal edge-count polynomials of colouring graphs imply equal chromatic polynomials. This broader problem asks for which pairs $(H, H')$ such a determination holds, motivated by Remark 10 in the paper.
Source paper
A note on graphs of $k$-colourings
Emma Hogan, Alex Scott, Youri Tamitegama, Jane Tan · 2024-02-29
https://arxiv.org/abs/2402.04237