Fixed-degree NP-completeness conjecture for non-synchronizing colorings
Let be a primitive -out graph, meaning a finite directed graph in which every vertex has out-degree and whose associated transition structure is primitive. Let be the set of colorings of , and define
Fixed-degree counting conjecture. The counting problem
is -complete on the class of primitive -out graphs, and remains -complete for fixed out-degree , already for .
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
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.