Random coloring evolution on graphs

DOI10.1007/S10114-010-6286-9MaRDI QIDQ5962274zbMATH OpenOpenAlexFDO

Authors Xinxing Chen, Jiangang Ying

Publication date 21 September 2010

Published in Acta Mathematica Sinica, English Series (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10114-010-6286-9

zbMATH Keywords

graphsMarkov chainsmartingalerandom coloring evolution

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20)

Review text

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.

Recommendations

• Evolutionary graph colouring
• Randomly coloring random graphs
• Coloring Random Intersection Graphs and Complex Networks
• Randomly colouring graphs (a combinatorial view)
• Edge flipping in graphs

Cites work

• f-colorings of some graphs of f-class 1
• Finding blocks and other patterns in a random coloring of ℤ
• First passage percolation for random colorings of \(\mathbb{Z}^ d\)
• scientific article; zbMATH DE number 3145626 (Why is no real title available?)
• scientific article; zbMATH DE number 3236503 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• On Spreading a Rumor

Cited in

(6)

• Evolutionary graph colouring
• Stochastic forms of non-negative matrices and Perron-regularity
• scientific article; zbMATH DE number 3928066 (Why is no real title available?)
• Edge flipping in the complete graph
• On the one dimensional ``learning from neighbours model
• Edge flipping in graphs

This page was built for publication: Random coloring evolution on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5962274)