The problem of vertex coloring in random graphs is studied using methods of statistical
physics and probability. Our analytical results are compared to those obtained by exact …

We study the graph coloring problem over random graphs of finite average connectivity c.
Given a number q of available colors, we find that graphs with low connectivity admit almost …

Methods of statistical mechanics are applied to two important NP-complete combinatorial
optimization problems. The first is the chromatic number problem, which seeks the minimal …

This paper describes a randomised algorithm for the NP-complete problem of 3-colouring
the vertices of a graph. The method is based on a model of repulsion in interacting particle …

We prove that a formula predicted on the basis of non-rigorous physics arguments
[Zdeborová and Krzakala: Phys. Rev. E (2007)] provides a lower bound on the chromatic …

We consider the problem of coloring the vertices of a large sparse random graph with a
given number of colors so that no adjacent vertices have the same color. Using the cavity …

We consider the problem of coloring Erdös-Rényi and regular random graphs of finite
connectivity using q colors. It has been studied so far using the cavity approach within the so …

We study the dynamics of a backtracking procedure capable of proving uncolourability of
graphs, and calculate its average running time T for sparse random graphs, as a function of …

We study combinatorial indicators related to the characteristic phase transitions associated
with the optimization problems of coloring the nodes of a graph with the minimum number of …

The NP-complete problems of partitioning and colouring of random graphs, with p partitions
and colours respectively, are mapped onto the statistical mechanical problem of p-state …