The coloring-graph family is a complete graph invariant
For a finite graph , let be its coloring graph for , and let count induced copies of a graph in these coloring graphs. Coloring-graph completeness conjecture. For any graph , the collection
uniquely determines . Equivalently, graphs and are isomorphic if and only if for every graph .
The conjecture asserts that the full family of coloring graphs, or equivalently all -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
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.