Graph Coloring with the Hopfield-clique Network

We approximately solve, by reduction to Maximum Clique, the graph k-coloring NP-hard problem in a binary weights Hopfield net special case. This network was used earlier to approximately solve Maximum Clique and some other NP-hard problems by reduction to Maximum Clique. We determine k-coloring approximation performance on random graphs and on one other distribution of "harder" graphs. We compare our work with earlier work and with theoretical estimates on random graphs. Our optimizing dynamics are discrete and converge in O(number of units) unit-switches. Our broad contribution is in optimizing a new problem in the same binary weights (0/-1) network, including the same dynamics, employed earlier for other problems. Our mapping does not admit any invalid solutions and is goodness-preserving in a formal sense. We also view the act of loading problem instances to be solved as associative memories storage. MAXIMUM CLIQUE. In a graph with undirected edges, a clique is a set of vertices s..