  While Boolean logic has been the backbone of digital information processing,
there are classes of computationally hard problems wherein this conventional
paradigm is fundamentally inefficient. Vertex coloring of graphs, belonging to
the class of combinatorial optimization represents such a problem; and is well
studied for its wide spectrum of applications in data sciences, life sciences,
social sciences and engineering and technology. This motivates alternate, and
more efficient non-Boolean pathways to their solution. Here, we demonstrate a
coupled relaxation oscillator based dynamical system that exploits the
insulator-metal transition in vanadium dioxide (VO2), to efficiently solve the
vertex coloring of graphs. By harnessing the natural analogue between
optimization, pertinent to graph coloring solutions, and energy minimization
processes in highly parallel, interconnected dynamical systems, we harness the
physical manifestation of the latter process to approximate the optimal
coloring of k-partite graphs. We further indicate a fundamental connection
between the eigen properties of a linear dynamical system and the spectral
algorithms that can solve approximate graph coloring. Our work not only
elucidates a physics-based computing approach but also presents tantalizing
opportunities for building customized analog co-processors for solving hard
problems efficiently.
