Solutions to all-colors problem on graph cellular automata (Q2325123)

Summary: The All-Ones Problem comes from the theory of \(\sigma^+\)-automata, which is related to graph dynamical systems as well as the Odd Set Problem in linear decoding. In this paper, we further study and compute the solutions to the ``All-Colors Problem,`` a generalization of ``All-Ones Problem,'' on some interesting classes of graphs which can be divided into two subproblems: Strong-All-Colors Problem and Weak-All-Colors Problem, respectively. We also introduce a new kind of All-Colors Problem, \(k\)-Random Weak-All-Colors Problem, which is relevant to both combinatorial number theory and cellular automata theory.