Graph coloring via synchronization of coupled oscillators

Abstract

In this brief, we study the possibility of coloring graphs by means of synchronized coupled oscillators. We consider an array of coupled oscillators as a graph by associating the oscillators to vertices and the coupling to edges. When the coupled array is synchronized, the phase of the oscillators can be considered as the color associated with the corresponding vertices. We prove that for connected 2-colorable graphs, we can construct a coupled array which generates the 2-coloring for that graph. For the general case, numerical simulation results with connected 3-colorable graphs suggest that the coupled array of oscillators can color graphs with a small number of colors in most cases. Some complexity issues of the system and comparisons to antivoter models of graph coloring will be discussed. We also conjecture that the system can be used to approximate the star chromatic number of the graph. © 1998 IEEE.