Finitely many coloring graphs determine the graph

At least 1 year old · documented by

For a finite graph GG, let Ck(G)\mathcal C_k(G) be its coloring graph. Finite coloring-graph determination conjecture. There exists a function f ⁣:Graphs⁡→Nf\colon \operatorname{Graphs}\to\mathbb N mapping finite graphs to natural numbers such that, for any graph GG, the collection

{Ck(G)}k=1f(G)\{\mathcal C_k(G)\}_{k=1}^{f(G)}

uniquely determines GG.

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 ff 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

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.