  We present the Douglas-Rachford algorithm as a successful heuristic for
solving graph coloring problems. Given a set of colors, these type of problems
consist in assigning a color to each node of a graph, in such a way that every
pair of adjacent nodes are assigned with different colors. We formulate the
graph coloring problem as an appropriate feasibility problem that can be
effectively solved by the Douglas-Rachford algorithm, despite the nonconvexity
arising from the combinatorial nature of the problem. Different modifications
of the graph coloring problem and applications are also presented. The good
performance of the method is shown in various computational experiments.
