# Collective dynamics of phase-repulsive oscillators solves graph coloring problem

arXiv: https://arxiv.org/abs/1909.06095 · HTML: https://mlsanity.com/paper/1909.06095/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Sep 2019.

## Built on by (most cited first, 1 of 1)

- [Different Paths, Same Destination: Designing New Physics-Inspired Dynamical Systems with Engineered Stability to Minimize the Ising Hamiltonian](https://mlsanity.com/paper/2504.06280/) (2025)

## Abstract (arXiv)

We show how to couple phase-oscillators on a graph so that collective dynamics "searches" for the coloring of that graph as it relaxes toward the dynamical equilibrium. This translates a combinatorial optimization problem (graph coloring) into a functional optimization problem (finding and evaluating the global minimum of dynamical non-equilibrium potential, done by the natural system's evolution). Using a sample of graphs, we show that our method can serve as a viable alternative to the traditional combinatorial algorithms. Moreover, we show that, with the same computational cost, our method efficiently solves the harder problem of improper coloring of weighed graphs.