Java Program to Implement the Vizing’s Theorem

0 0 2 minutes read

Vizing’s Theorem of graph theory states that every simple undirected graph has a chromatic index of one larger than the maximum degree ‘d’ of the graph. In simple meaning, the theorem states that the chromatic index can be either ‘d’ or ‘d’+1.

Chromatic Index of a graph is the minimum number of colors required to color the edges of the graph such that any two edges that share the same vertex have different colors.

Examples:

Input:

Output:

Chromatic Index = 3

Edge from 1 to 2 : Color 1

Edge from 2 to 3 : Color 2

Edge from 3 to 4 : Color 1

Edge from 4 to 1 : Color 2

Edge from 1 to 3 : Color 3

Algorithm:

Below is the step-by-step approach of the algorithm:-

Initialize the number of edges and the edge list.
Color the graph according to the Vizing’s Theorem.
Assign a color to an edge and check if any adjacent edges have the same color or not.
If any adjacent edge has the same color, then increment the color to try the next color for that edge.
Repeat till all the edges get it’s color according to the theorem.
Once done print the maximum value of color for all the edges and the colors of every edge.

Implementation of the above approach:

Java

// Java program to Implement
// Vizing's Theorem
  
import java.util.*;
  
public class chromaticIndex {
  
    // Function to find the chromatic index
    public void edgeColoring(int[][] edges, int e)
    {
        // Initialize edge to first
        // edge and color to color 1
        int i = 0, color = 1;
  
        // Repeat until all edges are done coloring
        while (i < e) {
  
            // Give the selected edge a color
            edges[i][2] = color;
  
            boolean flag = false;
  
            // Iterate through all others edges to check
            for (int j = 0; j < e; j++) {
  
                // Ignore if same edge
                if (j == i)
                    continue;
  
                // Check if one vertex is similar
                if ((edges[i][0] == edges[j][0])
                    || (edges[i][1] == edges[j][0])
                    || (edges[i][0] == edges[j][1])
                    || (edges[i][1] == edges[j][1])) {
  
                    // Check if color is similar
                    if (edges[i][2] == edges[j][2]) {
  
                        // Increment the color by 1
                        color++;
                        flag = true;
                        break;
                    }
                }
            }
  
            // If same color faced then repeat again
            if (flag == true) {
                continue;
            }
  
            // Or else proceed to a new vertex with color 1
            color = 1;
            i++;
        }
  
        // Check the maximum color from all the edge colors
        int maxColor = -1;
        for (i = 0; i < e; i++) {
            maxColor = Math.max(maxColor, edges[i][2]);
        }
  
        // Print the chromatic index
        System.out.println("Chromatic Index = " + maxColor);
        
        for (i = 0; i < e; i++)
        {
            System.out.println("Edge from " + edges[i][0]
                               + " to " + edges[i][1]
                               + " : Color " + edges[i][2]);
        }
    }
  
    // Driver code
    public static void main(String[] args)
    {
  
        // Number of edges
        int e = 5;
  
        // Edge list
        int[][] edges = new int[e][3];
  
        // Initialize all edge colors to 0
        for (int i = 0; i < e; i++) {
            edges[i][2] = -1;
        }
  
        // Edges
        edges[0][0] = 1;
        edges[0][1] = 2;
  
        edges[1][0] = 2;
        edges[1][1] = 3;
  
        edges[2][0] = 3;
        edges[2][1] = 4;
  
        edges[3][0] = 4;
        edges[3][1] = 1;
  
        edges[4][0] = 1;
        edges[4][1] = 3;
  
        // Run the function
        chromaticIndex c = new chromaticIndex();
        c.edgeColoring(edges, e);
    }
}

Output

Chromatic Index = 3
Edge from 1 to 2 : Color 1
Edge from 2 to 3 : Color 2
Edge from 3 to 4 : Color 1
Edge from 4 to 1 : Color 2
Edge from 1 to 3 : Color 3