The coloring-graph family is a complete graph invariant

At least 1 year old · documented by

For a finite graph GG, let Ck(G)\mathcal C_k(G) be its coloring graph for k≥1k\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)}k≥1\{\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.

References

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.