Graph coloring is a method of assigning labels, often called "colors", to elements of a graph subject to certain constraints. It is often used to solve problems in scheduling, register allocation, and map coloring.

Example 1: Vertex Coloring

Vertex coloring is the most common coloring problem. Here, each vertex of a graph is colored such that no two adjacent vertices share the same color.


class Graph {
    private int V; // Number of vertices
    private LinkedList adj[]; // Adjacency List

    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); // Undirected graph
    }

    void greedyColoring() {
        int result[] = new int[V];
        Arrays.fill(result, -1);
        result[0] = 0;

        boolean available[] = new boolean[V];
        Arrays.fill(available, true);

        for (int u = 1; u < V; u++) {
            Iterator it = adj[u].iterator();
            while (it.hasNext()) {
                int i = it.next();
                if (result[i] != -1)
                    available[result[i]] = false;
            }

            int cr;
            for (cr = 0; cr < V; cr++) {
                if (available[cr])
                    break;
            }

            result[u] = cr;
            Arrays.fill(available, true);
        }

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

Console Output:

Vertex 0 ---> Color 0
Vertex 1 ---> Color 1
Vertex 2 ---> Color 0
Vertex 3 ---> Color 1

Edge Coloring

Edge Coloring:

Edge coloring assigns a color to each edge so that no two edges sharing the same vertex have the same color. This is useful in problems like scheduling where resources are shared.


class EdgeColoring {
    private int V;
    private LinkedList adj[];

    EdgeColoring(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);
    }

    void edgeColoring() {
        int[] colors = new int[V];
        Arrays.fill(colors, -1);

        for (int u = 0; u < V; u++) {
            boolean[] available = new boolean[V];
            Arrays.fill(available, true);

            for (int i : adj[u]) {
                if (colors[i] != -1)
                    available[colors[i]] = false;
            }

            int cr;
            for (cr = 0; cr < V; cr++) {
                if (available[cr])
                    break;
            }

            colors[u] = cr;
        }

        for (int u = 0; u < V; u++)
            System.out.println("Edge " + u + " ---> Color " + colors[u]);
    }
}

Console Output:

Edge 0 ---> Color 0
Edge 1 ---> Color 1
Edge 2 ---> Color 0

Face Coloring

Face Coloring:

In face coloring, colors are assigned to the regions (faces) of a planar graph such that no two adjacent regions have the same color. This is often applied in map coloring.


// Simplified representation for face coloring
class FaceColoring {
    private int[][] faces;

    FaceColoring(int[][] faces) {
        this.faces = faces;
    }

    void colorFaces() {
        int[] colors = new int[faces.length];
        Arrays.fill(colors, -1);

        for (int i = 0; i < faces.length; i++) {
            boolean[] available = new boolean[faces.length];
            Arrays.fill(available, true);

            for (int j = 0; j < faces[i].length; j++) {
                int adjFace = faces[i][j];
                if (colors[adjFace] != -1)
                    available[colors[adjFace]] = false;
            }

            int cr;
            for (cr = 0; cr < faces.length; cr++) {
                if (available[cr])
                    break;
            }

            colors[i] = cr;
        }

        for (int i = 0; i < faces.length; i++)
            System.out.println("Face " + i + " ---> Color " + colors[i]);
    }
}

Console Output:

Face 0 ---> Color 0
Face 1 ---> Color 1
Face 2 ---> Color 0

Total Coloring

Total Coloring:

Total coloring is a comprehensive approach where both vertices and edges are colored. The goal is to ensure no adjacent or incident elements share the same color.


class TotalColoring {
    private int V;
    private LinkedList adj[];

    TotalColoring(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);
    }

    void totalColoring() {
        int[] vertexColors = new int[V];
        int[] edgeColors = new int[V];
        Arrays.fill(vertexColors, -1);
        Arrays.fill(edgeColors, -1);

        for (int u = 0; u < V; u++) {
            boolean[] available = new boolean[V];
            Arrays.fill(available, true);

            for (int i : adj[u]) {
                if (vertexColors[i] != -1)
                    available[vertexColors[i]] = false;
            }

            int cr;
            for (cr = 0; cr < V; cr++) {
                if (available[cr])
                    break;
            }

            vertexColors[u] = cr;
        }

        for (int u = 0; u < V; u++) {
            boolean[] available = new boolean[V];
            Arrays.fill(available, true);

            for (int i : adj[u]) {
                if (edgeColors[i] != -1)
                    available[edgeColors[i]] = false;
            }

            int cr;
            for (cr = 0; cr < V; cr++) {
                if (available[cr])
                    break;
            }

            edgeColors[u] = cr;
        }

        for (int u = 0; u < V; u++)
            System.out.println("Vertex " + u + " ---> Color " + vertexColors[u] + ", Edge ---> Color " + edgeColors[u]);
    }
}

Console Output:

Vertex 0 ---> Color 0, Edge ---> Color 1
Vertex 1 ---> Color 1, Edge ---> Color 0
Vertex 2 ---> Color 0, Edge ---> Color 1

Interval Graph Coloring

Interval Graph Coloring:

Interval graph coloring involves assigning colors to intervals in such a way that no overlapping intervals share the same color. This is often used in scheduling problems.


class IntervalGraphColoring {
    private int[][] intervals;

    IntervalGraphColoring(int[][] intervals) {
        this.intervals = intervals;
    }

    void colorIntervals() {
        int[] colors = new int[intervals.length];
        Arrays.fill(colors, -1);

        for (int i = 0; i < intervals.length; i++) {
            boolean[] available = new boolean[intervals.length];
            Arrays.fill(available, true);

            for (int j = 0; j < intervals.length; j++) {
                if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) {
                    if (colors[j] != -1)
                        available[colors[j]] = false;
                }
            }

            int cr;
            for (cr = 0; cr < intervals.length; cr++) {
                if (available[cr])
                    break;
            }

            colors[i] = cr;
        }

        for (int i = 0; i < intervals.length; i++)
            System.out.println("Interval [" + intervals[i][0] + ", " + intervals[i][1] + "] ---> Color " + colors[i]);
    }
}

Console Output:

Interval [1, 3] ---> Color 0
Interval [2, 5] ---> Color 1
Interval [4, 7] ---> Color 0