Fixed-degree NP-completeness conjecture for non-synchronizing colorings

Less than 1 year old · traced to

Let GG be a primitive kk-out graph, meaning a finite directed graph in which every vertex has out-degree kk and whose associated transition structure is primitive. Let C(G)\mathcal C(G) be the set of colorings of GG, and define

#NSC(G):=∣{χ∈C(G):χ(G) is non-synchronizing}∣.\#\mathrm{NSC}(G):=\bigl|\{\chi\in\mathcal C(G):\chi(G)\text{ is non-synchronizing}\}\bigr|.

Fixed-degree counting conjecture. The counting problem

G⟼#NSC(G)G\longmapsto\#\mathrm{NSC}(G)

is #P\#P-complete on the class of primitive kk-out graphs, and remains #P\#P-complete for fixed out-degree kk, already for k=2k=2.

This is presented after a proof of the corresponding decision problem and concerns the exact number of non-synchronizing colorings. The source provides no resolution status for this counting claim.

References

Primary source

Daniele D'Angeli and Emanuele Rodaro, “On totally synchronizing graphs”, arXiv:2607.17335 (2026).

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.