Algorithms for Solving Large Random Graphs

Abstract

The problem of vertex colouring in large random graphs is unlikely to be an easy task. Given a number of available colours (in our study we used three colours), there are two relevant values of the graph connectivity delimiting three different states: when it is quite easy to find a solution, when it is very hard and when it is almost impossible. We adapt an existing algorithm using message-passing techniques to graphs and hypergraphs (here hypergraph means that the graph contains edges linking three vertices) and study its behaviour in the different states with large random graphs. We then compare it with an exact enumeration algorithm on small systems.