This Java program demonstrates how to color a graph using a greedy algorithm to minimize the number of colors used. The greedy coloring algorithm chooses the smallest available color for each vertex. The order in which vertices are considered can significantly affect the number of colors used, but this implementation simply uses the natural order of vertices.

Java Code

import java.util.Arrays;
import java.util.LinkedList;

public class GraphColoring {
    private int vertices; // Number of vertices in the graph
    private LinkedList<Integer>[] adjList; // Adjacency list representation of the graph

    public GraphColoring(int numVertices) {
        this.vertices = numVertices;
        adjList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    // Function to add an edge to the graph
    public void addEdge(int v, int w) {
        adjList[v].add(w);
        adjList[w].add(v); // Because the graph is undirected
    }

    // Function to assign colors to vertices
    public void colorGraph() {
        int[] result = new int[vertices]; // Store the result of colors assigned to vertices
        Arrays.fill(result, -1); // Initialize all vertices as unassigned
        result[0] = 0; // Assign the first color to first vertex

        // A temporary array to store the available colors. False value of available[cr]
        // indicates that the color cr is assigned to one of its adjacent vertices
        boolean[] available = new boolean[vertices];
        Arrays.fill(available, true);

        // Assign colors to remaining V-1 vertices
        for (int u = 1; u < vertices; u++) {
            // Process all adjacent vertices and flag their colors as unavailable
            for (int i : adjList[u]) {
                if (result[i] != -1) // If the color is assigned to the vertex
                    available[result[i]] = false;
            }

            // Find the first available color
            int cr;
            for (cr = 0; cr < vertices; cr++) {
                if (available[cr]) break;
            }

            result[u] = cr; // Assign the found color

            // Reset the values back to true for the next iteration
            Arrays.fill(available, true);
        }

        // Print the result
        for (int u = 0; u < vertices; u++)
            System.out.println("Vertex " + u + " --->  Color " + result[u]);
    }

    public static void main(String[] args) {
        GraphColoring g = new GraphColoring(5);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(3, 4);
        g.addEdge(4, 0);
        g.addEdge(0, 2);

        g.colorGraph();
    }
}

Explanation of the Code

The program defines a class GraphColoring with methods to add edges and color the graph. The graph is represented using an adjacency list. Here’s a breakdown of the program structure:

• Graph Initialization: The constructor initializes the adjacency list for each vertex.
• Edge Addition: The addEdge method populates the adjacency list to create a bidirectional connection between vertices, reflecting an undirected graph.
• Coloring Method: The colorGraph method implements the greedy coloring algorithm. It starts by assigning the first color to the first vertex and then proceeds to assign the lowest available color to each subsequent vertex, ensuring that no two adjacent vertices share the same color.

This implementation is effective for educational and simple practical applications. However, for graphs with particular structures or requirements, a more sophisticated algorithm might be necessary to ensure optimal coloring.