Simple RLF graph coloring solver

RLFSolver.java

import java.util.*;

public class RLFSolver {

    public static List<Vertex> getCandidates(Graph g)
    {
        List<Vertex> candidates;
        List<Vertex> included = new ArrayList<>();
        List<Vertex> excluded = new ArrayList<>();
        Random r = new Random();

        candidates = g.getListOfUncoloredVertex();
        included.clear();
        excluded.clear();
        while (!candidates.isEmpty())
        {
            final int candidates_count = candidates.size();
            int max_adjacent_edges = Integer.MIN_VALUE;
            Vertex candidate = null;
            if (!excluded.isEmpty())
            {
                for (final Vertex vx : candidates)
                {
                    int adjacent_edges = 0;
                    for (final Vertex v : vx.getEdges())
                    {
                        if (excluded.contains(v))
                            adjacent_edges++;
                    }
                    if (adjacent_edges >= max_adjacent_edges)
                    {
                        candidate = vx;
                        max_adjacent_edges = adjacent_edges;
                    }
                }
            }
            if (candidate == null)
                candidate = candidates.get(r.nextInt(candidates_count));

            candidates.remove(candidate);
            candidates.removeAll(candidate.getEdges());

            included.add(candidate);
            excluded.addAll(candidate.getEdges());
        }
        return included;
    }

    public static String solve(Graph g)
    {

        int minimal_coloring = g.getNodesCount();
        int current_color = 0;
        String solution = "";
        for (int i = 0; i < 1; i++)
        {
            while (!g.isValid() && g.countClique() <= minimal_coloring)
            {
                final List<Vertex> vxs = getCandidates(g);
                for (Vertex vx : vxs) vx.setColor(current_color);
                current_color++;
            }
            System.err.println(g.countClique());
            if (g.countClique() < minimal_coloring)
            {
                minimal_coloring = g.countClique();
                solution = g.printSolution();
            }
            g.resetColors();
            current_color = 0;
        }

        return solution;

    }

}