Experiments in the Dynamics of Phase Coupled Oscillators When Applied to Graph Colouring

Lee, S. and Lister, R.

This paper examines the capacity of networks of phase coupled oscillators to coordinate activity in a parallel, distributed fashion. To benchmark these networks of oscillators, we present empirical results from a study of the capacity of such networks to colour graphs. We generalise the update equation of Aihara et al. to an equation that can be applied to graphs requiring multiple colours. We find that our simple multi-phase model can colour some types of graphs, especially complete graphs and complete k-partite graphs with equal or a near equal number of vertices in each partition. A surprising empirical result is that the effectiveness of the approach appears to be more dependent upon the topology of the graph than the size of the graph.

Cite as: Lee, S. and Lister, R. (2008). Experiments in the Dynamics of Phase Coupled Oscillators When Applied to Graph Colouring. In Proc. Thirty-First Australasian Computer Science Conference (ACSC 2008), Wollongong, NSW, Australia. CRPIT, 74. Dobbie, G. and Mans, B., Eds. ACS. 83-89.

(from crpit.com) (local if available)