Finitely many coloring graphs determine the graph

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 ⁣:GraphsNf\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.

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

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.