The following submission rules apply For those questions re

The following submission rules apply:

·    For those questions requiring programs, the solutions must be implemented using JavaScript or Java.

o Appropriate self-documenting comments in the source code are mandatory, consistent with good programming practices.

o Solutions must be provided in plain text so that formatting is not lost.

·    All answers must be provided in this document.

·    Sources must be given accurate and complete citations sufficient for the instructor to find and confirm them.

1 Design a greedy strategy for finding a proper coloring of a graph using D(G) + 1 colors, where D(G) denotes the maximum degree of a vertex.

Solution

1. Color first vertex with first color.

2. Do following for remaining V-1 vertices.

         a) Consider the currently picked vertex and color it with the

             lowest numbered color that has not been used on any previously

             colored vertices adjacent to it. If all previously used colors

             appear on vertices adjacent to v, assign a new color to it.

import java.io.*;

import java.util.*;

import java.util.LinkedList;

class Graph

{

    private int V;  

    private LinkedList<Integer> adj[];

    Graph(int v)

    {

        V = v;

        adj = new LinkedList[v];

        for (int i=0; i<v; ++i)

            adj[i] = new LinkedList();

    }

    void addEdge(int v,int w)

    {

        adj[v].add(w);

        adj[w].add(v); //Graph is undirected

    }

    void greedyColoring()

    {

        int result[] = new int[V];

        result[0] = 0;

        for (int u = 1; u < V; u++)

            result[u] = -1; // no color is assigned to u

        boolean available[] = new boolean[V];

        for (int cr = 0; cr < V; cr++)

            available[cr] = false;

        for (int u = 1; u < V; u++)

        {

            Iterator<Integer> it = adj[u].iterator() ;

            while (it.hasNext())

            {

                int i = it.next();

                if (result[i] != -1)

                    available[result[i]] = true;

            }

            int cr;

            for (cr = 0; cr < V; cr++)

                if (available[cr] == false)

                    break;

            result[u] = cr;

            it = adj[u].iterator() ;

            while (it.hasNext())

            {

                int i = it.next();

                if (result[i] != -1)

                    available[result[i]] = false;

            }

        }

        for (int u = 0; u < V; u++)

            System.out.println(\"Vertex \" + u + \" ---> Color \"

                                + result[u]);

    }

    public static void main(String args[])

    {

        Graph g1 = new Graph(5);

        g1.addEdge(0, 1);

        g1.addEdge(0, 2);

        g1.addEdge(1, 2);

        g1.addEdge(1, 3);

        g1.addEdge(2, 3);

        g1.addEdge(3, 4);

        System.out.println(\"Coloring of graph 1\");

        g1.greedyColoring();

        System.out.println();

        Graph g2 = new Graph(5);

        g2.addEdge(0, 1);

        g2.addEdge(0, 2);

        g2.addEdge(1, 2);

        g2.addEdge(1, 4);

        g2.addEdge(2, 4);

        g2.addEdge(4, 3);

        System.out.println(\"Coloring of graph 2 \");

        g2.greedyColoring();

    }

}