  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.
