The coloring-graph family is a complete graph invariant

For a finite graph GG, let Ck(G)\mathcal C_k(G) be its coloring graph for k1k\geq 1, and let πG(H)\pi_G^{(H)} count induced copies of a graph HH in these coloring graphs. Coloring-graph completeness conjecture. For any graph GG, the collection

{Ck(G)}k1\{\mathcal C_k(G)\}_{k\geq 1}

uniquely determines GG. Equivalently, graphs G1G_1 and G2G_2 are isomorphic if and only if πG1(H)=πG2(H)\pi_{G_1}^{(H)}=\pi_{G_2}^{(H)} for every graph HH.

The conjecture asserts that the full family of coloring graphs, or equivalently all HH-polynomials, is a complete invariant, despite discarding the individual coloring data. The paper presents it as open.

Sources & referencesView supporting material

Primary source

Shamil Asgarli, Sara Krehbiel, Howard W. Levinson and Heather M. Russell, “Counting subgraphs of coloring graphs”, arXiv:2401.12883 (2025).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.