Random coloring evolution on graphs (Q5962274)

After an Introduction, in Section 2 is built and investigated a model which simulates how people influence each other in a connection network. It also simulates how colors evolve on a graph according to some probability law of transition and hence it is called random coloring in the title. It is built a Markov chain running on the configuration space of a connected and undirected graph \(G\). Then, it is proved that the Markov chain will be eventually absorbed in two traps if and only if \(G\) contains an odd cycles and it is also calculated the probability that starting from any initial state the Markov chain goes into each trap. For the case when \(G\) is bipartite. the corresponding results are derived in Section 3. The authors emphasize that the main tool employed in this paper is to construct suitable martingales, which makes it different from the considered references.