The coloring-graph family is a complete graph invariant
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.