The restrained-polynomial deck reconstructs the chromatic polynomial

Let G1G_1 and G2G_2 be graphs. For each vertex vv, let ρrv(2)(k)\rho_{r_v^{(2)}}(k) denote the corresponding restrained chromatic polynomial, and consider the multiset of these polynomials over the vertices. Restrained-deck reconstruction conjecture. If G1G_1 and G2G_2 share the same multiset

{ρrv(2)(k)}vV(G1)={ρrv(2)(k)}vV(G2),\{\rho_{r_v^{(2)}}(k)\}_{v\in V(G_1)}=\{\rho_{r_v^{(2)}}(k)\}_{v\in V(G_2)},

then πG1(k)=πG2(k)\pi_{G_1}(k)=\pi_{G_2}(k).

This is compared with the Polynomial Reconstruction Problem, which asks whether the chromatic polynomial can be recovered from the vertex-deletion deck. The status of this restrained-polynomial version is unclear in the paper.

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.