M-Coloring Algorithm in JavaScript: Graph Coloring with Backtracking

M-Coloring Graph Algorithm in JavaScript

The M-Coloring problem is a graph coloring algorithm where we color a graph using at most M different colors such that no two adjacent nodes have the same color.

🔹 Problem Statement

Given an undirected graph represented as an adjacency matrix and an integer M (number of colors), the goal is to assign colors to vertices such that no two adjacent vertices share the same color.

🔍 Algorithm Steps

• Assign a color to each vertex.
• Ensure no two adjacent vertices have the same color.
• Use backtracking to try different color assignments.
• Stop when all vertices are colored or return null if not possible.

🛠️ JavaScript Implementation

    
      function mColoring(graph, m) {
        const colors = new Array(graph.length).fill(0);

        function isSafe(vertex, color) {
          for (let i = 0; i < graph.length; i++) {
            if (graph[vertex][i] && colors[i] === color) {
              return false;
            }
          }
          return true;
        }

        function solveColoring(vertex = 0) {
          if (vertex === graph.length) {
            return true;
          }

          for (let color = 1; color <= m; color++) {
            if (isSafe(vertex, color)) {
              colors[vertex] = color;
              if (solveColoring(vertex + 1)) {
                return true;
              }
              colors[vertex] = 0;
            }
          }
          return false;
        }

        return solveColoring() ? colors : null;
      }
    
  

📌 Example Usage

    
      import { mColoring } from "./mColoring.js";

      const graph = [
        [0, 1, 1, 1],
        [1, 0, 1, 0],
        [1, 1, 0, 1],
        [1, 0, 1, 0],
      ];

      const m = 3;
      const result = mColoring(graph, m);

      console.log(result ? "Graph can be colored:" + result : "Graph coloring not possible");
    
  

⏳ Time Complexity

The worst-case time complexity is O(M^N) because the algorithm explores all possible ways to color N vertices with M colors using backtracking.

📌 Real-World Applications

• ✅ Scheduling Problems (Exams, Jobs, Meetings)
• ✅ Map Coloring (Assigning different colors to regions on a map)
• ✅ Register Allocation in compilers