public void colorGraph(){
        
        Graph<Integer> graph = new Graph<Integer>(false);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(1, 4);
        graph.addEdge(4, 6);
        graph.addEdge(1, 7);
        graph.addEdge(1, 8);
        graph.addEdge(2, 9);
        graph.addEdge(1, 3);
        graph.addEdge(3, 4);
        graph.addEdge(2,4);
        graph.addEdge(3,7);

        Map<String,Boolean> colorsUsed = new HashMap<String,Boolean>();
        colorsUsed.put("Green", false);
        colorsUsed.put("Blue", false);
        colorsUsed.put("Red", false);
        colorsUsed.put("Yellow", false);
        
        Map<Long,String> colorsAssigned = new HashMap<Long,String>();
        
        Collection<Vertex<Integer>> allVertex = graph.getAllVertex();
        
        for(Vertex<Integer> v : allVertex){
            List<Vertex<Integer>> adjacentVertexes = v.getAdjacentVertexes();
            for(Vertex<Integer> adjacentVertex : adjacentVertexes){
                String color = colorsAssigned.get(adjacentVertex.getId());
                if(color != null){
                    assignColor(color,colorsUsed);
                }
            }
            String color = getUnusedColor(colorsUsed);
            colorsAssigned.put(v.getId(), color);
            resetColor(colorsUsed);
        }
        
        System.out.println(colorsAssigned);
    }
http://www.geeksforgeeks.org/graph-coloring-set-2-greedy-algorithm/
src/com/interview/graph/GraphColoring.java