Finitely many coloring graphs determine the graph
For a finite graph , let be its coloring graph. Finite coloring-graph determination conjecture. There exists a function mapping finite graphs to natural numbers such that, for any graph , the collection
uniquely determines .
This is presented as a seemingly stronger finite version of the coloring-graph completeness conjecture: because graphs are finite, the authors expect finitely many colors to suffice. The paper does not resolve whether such an exists.
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.