Application of Synchronized Oscillators to Graph Coloring

In this section we look at how a network of synchronizing coupled relaxation oscillators can be used to solve the graph coloring problem. The presentation is taken from [Wu 1998].

We use the state equations and definitions described in this section. The state equations are given by:

where f(x,t) satisfies (y-z)^TV(f(y,t)+C(t)y-f(z,t)-C(t)z) ≤ -α||y-z||² for some α > 0 and VC(t) is positive definite. For the state equations to encode a graph, we set G = A+D where A is the adjacency matrix of a graph and D is the diagonal matrix of vertex degrees. Note that the Laplacian matrix of the graph is D-A.

Theorem 1 [Wu 1998]: If the graph is 2-colorable and 1/κ is less than the smallest nonzero eigenvalue of L = D-A (i.e. the algebraic connectivity of the graph), then the system of coupled dynamical system solves the graph coloring problem in the sense that the trajectories converge to a synchronized state where oscillators that are connected by an edge are at opposite phase.

Since the algebraic connectivity of a graph of N vertices is equal or larger than (2(1-cos(π /N)), we can pick κ > 1/(2-2cos(π/N)) ≈ (N/π)².

When the graph is not 2-colorable, i.e., the chromatic number of the graph is 3 or more, the oscillators are not necessarily at opposite phase, and we need to partition the phases into clusters in order to find a valid coloring. The distance function between the phases are modulo 2π as the topology is the unit circle S¹.

The star chromatic number [Vince 1988] is defined as the infinum of the k-chromatic numbers, where the k-chromatic numbers correspond to colors being elements in R/kZ, with colors as far apart as possible. if X is the chromatic number of a graph, then the star chromatic number X* satisfies X-1 < X* ≤ X. Since R/kZ is topologically equivalent to S¹, this leads to the following conjecture.

Conjecture [Wu 1998]: The steady state phase of the coupled network of oscillators can be used to compute the star chromatic number using the equation:

Since X* = 2 for bipartite graphs, the theorem above shows that this conjecture is true for bipartite graphs.

References

[Vince 1988] A. Vince. Star chromatic number. Journal of Graph Theory, vol. 12, no. 4, pp. 551-559, 1988.

[Wu 1998] C. W. Wu. Graph Coloring via Synchronization of Coupled Oscillators. IEEE Transactions on Circuits and Systems, Part I, vol. 45, no. 9 pp. 974-978, 1998.

Copyright 2020 by Chai Wah Wu.