Algorithm to Find Chromatic Numbers
There are several algorithms to find the chromatic number of a graph, each with its own strengths and weaknesses in terms of complexity:
1. Finding Chromatic Numbers using Greedy Algorithm:
- Idea: Assign colors to vertices sequentially, choosing the first available color (not used by any neighbors) for each vertex.
- Complexity: O(V + E), where V is the number of vertices and E is the number of edges.
- Pros: Simple to implement, fast for sparse graphs.
- Cons: Doesn’t guarantee optimal solution for all graphs, often overestimates the chromatic number.
Implementation:
C++
#include <algorithm> #include <iostream> #include <unordered_set> #include <vector> using namespace std; // Function to find the chromatic number using the greedy // coloring algorithm int greedyColoring( const vector<vector< int > >& graph) { int n = graph.size(); vector< int > colors(n, -1); for ( int v = 0; v < n; ++v) { unordered_set< int > usedColors; // Check neighbors and mark their colors as used for ( int neighbor : graph[v]) { if (colors[neighbor] != -1) { usedColors.insert(colors[neighbor]); } } // Find the smallest available color for ( int color = 1;; ++color) { if (usedColors.find(color) == usedColors.end()) { colors[v] = color; break ; } } } // Find the maximum color used (chromatic number) int chromaticNumber = *max_element(colors.begin(), colors.end()) + 1; return chromaticNumber; } int main() { // Sample graph represented as an adjacency list vector<vector< int > > graph = { { 1, 2, 3 }, { 0, 2 }, { 0, 1, 3 }, { 0, 2 } }; // Find and output the chromatic number int chromaticNumber = greedyColoring(graph); cout << "Chromatic Number: " << chromaticNumber << endl; return 0; } |
Java
// Java Implementation import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; public class GreedyColoring { // Function to find the chromatic number using the greedy // coloring algorithm public static int greedyColoring(List<List<Integer>> graph) { int n = graph.size(); int [] colors = new int [n]; for ( int i = 0 ; i < n; i++) { colors[i] = - 1 ; } for ( int v = 0 ; v < n; v++) { Set<Integer> usedColors = new HashSet<>(); // Check neighbors and mark their colors as used for ( int neighbor : graph.get(v)) { if (colors[neighbor] != - 1 ) { usedColors.add(colors[neighbor]); } } // Find the smallest available color int color; for (color = 1 ; ; color++) { if (!usedColors.contains(color)) { colors[v] = color; break ; } } } // Find the maximum color used (chromatic number) int chromaticNumber = 0 ; for ( int color : colors) { chromaticNumber = Math.max(chromaticNumber, color); } return chromaticNumber + 1 ; } public static void main(String[] args) { // Sample graph represented as an adjacency list List<List<Integer>> graph = new ArrayList<>(); graph.add( new ArrayList<>(List.of( 1 , 2 , 3 ))); graph.add( new ArrayList<>(List.of( 0 , 2 ))); graph.add( new ArrayList<>(List.of( 0 , 1 , 3 ))); graph.add( new ArrayList<>(List.of( 0 , 2 ))); // Find and output the chromatic number int chromaticNumber = greedyColoring(graph); System.out.println( "Chromatic Number: " + chromaticNumber); } } // This code is contributed by Tapesh(tapeshdu420) |
C#
using System; using System.Collections.Generic; using System.Linq; public class GreedyColoring { // Function to find the chromatic number using the greedy // coloring algorithm public static int FindChromaticNumber(List<List< int >> graph) { int n = graph.Count; int [] colors = new int [n]; for ( int i = 0; i < n; i++) { colors[i] = -1; } for ( int v = 0; v < n; v++) { HashSet< int > usedColors = new HashSet< int >(); // Check neighbors and mark their colors as used foreach ( int neighbor in graph[v]) { if (colors[neighbor] != -1) { usedColors.Add(colors[neighbor]); } } // Find the smallest available color int color; for (color = 1; ; color++) { if (!usedColors.Contains(color)) { colors[v] = color; break ; } } } // Find the maximum color used (chromatic number) int chromaticNumber = colors.Max(); return chromaticNumber + 1; } public static void Main( string [] args) { // Sample graph represented as an adjacency list List<List< int >> graph = new List<List< int >> { new List< int > { 1, 2, 3 }, new List< int > { 0, 2 }, new List< int > { 0, 1, 3 }, new List< int > { 0, 2 } }; // Find and output the chromatic number int chromaticNumber = FindChromaticNumber(graph); Console.WriteLine( "Chromatic Number: " + chromaticNumber); } } |
Javascript
// Function to find the chromatic number // using the greedy coloring algorithm function greedyColoring(graph) { const n = graph.length; const colors = new Array(n).fill(-1); for (let v = 0; v < n; ++v) { const usedColors = new Set(); // Check neighbors and mark // their colors as used for (const neighbor of graph[v]) { if (colors[neighbor] !== -1) { usedColors.add(colors[neighbor]); } } // Find the smallest available // color let color = 1; while ( true ) { if (!usedColors.has(color)) { colors[v] = color; break ; } color++; } } // Find the maximum color used // (chromatic number) const chromaticNumber = Math.max(...colors) + 1; return chromaticNumber; } // Sample graph represented as an // adjacency list const graph = [ [1, 2, 3], [0, 2], [0, 1, 3], [0, 2] ]; // Find and output the chromatic number const chromaticNumber = greedyColoring(graph); console.log( "Chromatic Number: " + chromaticNumber); |
Python3
def greedy_coloring(graph): n = len (graph) colors = [ - 1 ] * n for v in range (n): used_colors = set () # Check neighbors and mark their colors as used for neighbor in graph[v]: if colors[neighbor] ! = - 1 : used_colors.add(colors[neighbor]) # Find the smallest available color color = 1 while True : if color not in used_colors: colors[v] = color break color + = 1 # Find the maximum color used (chromatic number) chromatic_number = max (colors) + 1 return chromatic_number # Sample graph represented as an adjacency list graph = [[ 1 , 2 , 3 ], [ 0 , 2 ], [ 0 , 1 , 3 ], [ 0 , 2 ]] # Find and output the chromatic number chromatic_number = greedy_coloring(graph) print ( "Chromatic Number:" , chromatic_number) |
Output
Chromatic Number: 4
2. Finding Chromatic Numbers using Backtracking Algorithm:
- Idea: Systematically explore all possible colorings by assigning colors to each vertex and backtracking if an invalid coloring is encountered.
- Complexity: O(V! * K^V), where K is the number of available colors and V is the number of vertices. This can be exponential for large graphs.
- Pros: Guarantees optimal solution, can be modified for specific constraints.
- Cons: Very slow for large graphs, impractical for real-world scenarios.
Implementation:
C++
#include <iostream> #include <unordered_set> #include <vector> using namespace std; // Function to check if it's safe to color a vertex with a // given color bool isSafe( int v, const vector<vector< int > >& graph, const vector< int >& color, int c) { for ( int neighbor : graph[v]) { if (color[neighbor] == c) { return false ; // If any adjacent vertex has the // same color, it's not safe } } return true ; } // Backtracking function to find a valid coloring bool graphColoringUtil( int v, const vector<vector< int > >& graph, vector< int >& color, int m) { if (v == graph.size()) { return true ; // All vertices are colored, a solution // is found } for ( int c = 1; c <= m; ++c) { if (isSafe(v, graph, color, c)) { color[v] = c; // Recur for the next vertices if (graphColoringUtil(v + 1, graph, color, m)) { return true ; } // Backtrack color[v] = 0; } } return false ; // No solution found for this coloring } // Main function to find chromatic number int graphColoring( const vector<vector< int > >& graph, int m) { int n = graph.size(); vector< int > color(n, 0); if (!graphColoringUtil(0, graph, color, m)) { cout << "No feasible solution exists" ; return 0; } // Print the solution cout << "Vertex colors: " ; for ( int c : color) { cout << c << " " ; } cout << endl; // Count unique colors to determine chromatic number unordered_set< int > uniqueColors(color.begin(), color.end()); return uniqueColors.size(); } int main() { // Sample graph represented as an adjacency list vector<vector< int > > graph = { { 1, 2, 3 }, { 0, 2 }, { 0, 1, 3 }, { 0, 2 } }; // Set the maximum number of colors int maxColors = 3; // Find and output the chromatic number int chromaticNumber = graphColoring(graph, maxColors); cout << "Chromatic Number: " << chromaticNumber << endl; return 0; } |
Java
import java.util.*; public class GraphColoring { // Function to check if it's safe to color a vertex with a given color static boolean isSafe( int v, List<List<Integer>> graph, int [] color, int c) { for ( int neighbor : graph.get(v)) { if (color[neighbor] == c) { return false ; // If any adjacent vertex has the same color, it's not safe } } return true ; } // Backtracking function to find a valid coloring static boolean graphColoringUtil( int v, List<List<Integer>> graph, int [] color, int m) { if (v == graph.size()) { return true ; // All vertices are colored, a solution is found } for ( int c = 1 ; c <= m; ++c) { if (isSafe(v, graph, color, c)) { color[v] = c; // Recur for the next vertices if (graphColoringUtil(v + 1 , graph, color, m)) { return true ; } // Backtrack color[v] = 0 ; } } return false ; // No solution found for this coloring } // Main function to find chromatic number static int graphColoring(List<List<Integer>> graph, int m) { int n = graph.size(); int [] color = new int [n]; if (!graphColoringUtil( 0 , graph, color, m)) { System.out.println( "No feasible solution exists" ); return 0 ; } // Print the solution StringBuilder result = new StringBuilder( "Vertex colors: " ); for ( int c : color) { result.append(c).append( " " ); } System.out.println(result); // Count unique colors to determine chromatic number Set<Integer> uniqueColors = new HashSet<>(); for ( int c : color) { uniqueColors.add(c); } return uniqueColors.size(); } // Main function public static void main(String[] args) { // Sample graph represented as an adjacency list List<List<Integer>> graph = new ArrayList<>(); graph.add(Arrays.asList( 1 , 2 , 3 )); graph.add(Arrays.asList( 0 , 2 )); graph.add(Arrays.asList( 0 , 1 , 3 )); graph.add(Arrays.asList( 0 , 2 )); // Set the maximum number of colors int maxColors = 3 ; // Find and output the chromatic number int chromaticNumber = graphColoring(graph, maxColors); System.out.println( "Chromatic Number: " + chromaticNumber); } } |
C#
using System; using System.Collections.Generic; class Program { // Function to check if it's safe to color a vertex with // a given color static bool IsSafe( int v, List<List< int > > graph, List< int > color, int c) { foreach ( int neighbor in graph[v]) { if (color[neighbor] == c) { return false ; // If any adjacent vertex has // the same color, it's not // safe } } return true ; } // Backtracking function to find a valid coloring static bool GraphColoringUtil( int v, List<List< int > > graph, List< int > color, int m) { if (v == graph.Count) { return true ; // All vertices are colored, a // solution is found } for ( int c = 1; c <= m; ++c) { if (IsSafe(v, graph, color, c)) { color[v] = c; // Recur for the next vertices if (GraphColoringUtil(v + 1, graph, color, m)) { return true ; } // Backtrack color[v] = 0; } } return false ; // No solution found for this coloring } // Main function to find chromatic number static int GraphColoring(List<List< int > > graph, int m) { int n = graph.Count; List< int > color = new List< int >( new int [n]); if (!GraphColoringUtil(0, graph, color, m)) { Console.WriteLine( "No feasible solution exists" ); return 0; } // Print the solution Console.Write( "Vertex colors: " ); foreach ( int c in color) { Console.Write(c + " " ); } Console.WriteLine(); // Count unique colors to determine chromatic number HashSet< int > uniqueColors = new HashSet< int >(color); return uniqueColors.Count; } static void Main( string [] args) { // Sample graph represented as an adjacency list List<List< int > > graph = new List<List< int > >{ new List< int >{ 1, 2, 3 }, new List< int >{ 0, 2 }, new List< int >{ 0, 1, 3 }, new List< int >{ 0, 2 } }; // Set the maximum number of colors int maxColors = 3; // Find and output the chromatic number int chromaticNumber = GraphColoring(graph, maxColors); Console.WriteLine( "Chromatic Number: " + chromaticNumber); } } |
Javascript
// Function to check if it's safe to color a vertex with a given color function isSafe(v, graph, color, c) { for (let neighbor of graph[v]) { if (color[neighbor] === c) { return false ; // If any adjacent vertex has the same color, it's not safe } } return true ; } // Backtracking function to find a valid coloring function graphColoringUtil(v, graph, color, m) { if (v === graph.length) { return true ; // All vertices are colored, a solution is found } for (let c = 1; c <= m; ++c) { if (isSafe(v, graph, color, c)) { color[v] = c; // Recur for the next vertices if (graphColoringUtil(v + 1, graph, color, m)) { return true ; } // Backtrack color[v] = 0; } } return false ; // No solution found for this coloring } // Main function to find chromatic number function graphColoring(graph, m) { const n = graph.length; const color = new Array(n).fill(0); if (!graphColoringUtil(0, graph, color, m)) { console.log( "No feasible solution exists" ); return 0; } // Print the solution let result = "Vertex colors: " ; for (let c of color) { result += c + " " ; } console.log(result); // Count unique colors to determine chromatic number const uniqueColors = new Set(color); return uniqueColors.size; } // Main function function main() { // Sample graph represented as an adjacency list const graph = [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]; // Set the maximum number of colors const maxColors = 3; // Find and output the chromatic number const chromaticNumber = graphColoring(graph, maxColors); console.log( "Chromatic Number: " + chromaticNumber); } // Call the main function main(); |
Python3
from typing import List , Set def is_safe(v, graph, color, c): for neighbor in graph[v]: if color[neighbor] = = c: return False # If any adjacent vertex has the same color, it's not safe return True def graph_coloring_util(v, graph, color, m): if v = = len (graph): return True # All vertices are colored, a solution is found for c in range ( 1 , m + 1 ): if is_safe(v, graph, color, c): color[v] = c # Recur for the next vertices if graph_coloring_util(v + 1 , graph, color, m): return True # Backtrack color[v] = 0 return False # No solution found for this coloring def graph_coloring(graph, m): n = len (graph) color = [ 0 ] * n if not graph_coloring_util( 0 , graph, color, m): print ( "No feasible solution exists" ) return 0 # Print the solution print ( "Vertex colors:" , end = " " ) for c in color: print (c, end = " " ) print () # Count unique colors to determine chromatic number unique_colors = set (color) return len (unique_colors) if __name__ = = "__main__" : # Sample graph represented as an adjacency list graph = [[ 1 , 2 , 3 ], [ 0 , 2 ], [ 0 , 1 , 3 ], [ 0 , 2 ]] # Set the maximum number of colors max_colors = 3 # Find and output the chromatic number chromatic_number = graph_coloring(graph, max_colors) print ( "Chromatic Number:" , chromatic_number) |
Output
Vertex colors: 1 2 3 2 Chromatic Number: 3
3. Finding Chromatic Numbers using Heuristic Algorithms:
- Idea: Utilize various heuristics to guide the search for a valid coloring, often combining greedy approaches with elements of backtracking or other techniques.
- Examples: Simulated annealing, genetic algorithms, tabu search.
- Complexity: Varies depending on the specific heuristic, usually between O(V * E) and O(V! * K^V).
- Pros: Can find good solutions for large graphs in reasonable time, offer a balance between speed and accuracy.
- Cons: No guarantee of optimality, performance depends on the chosen heuristic and its parameters.
4. Finding Chromatic Numbers using Exact Algorithms:
- Examples: Branch and bound, integer linear programming.
- Complexity: Typically exponential in the worst case, but can be effective for specific graph classes.
- Pros: Guaranteed to find the optimal solution, valuable for theoretical understanding.
- Cons: Computationally expensive, often impractical for large graphs due to high runtime.
Chromatic Number of a Graph | Graph Colouring
Graph coloring is a fundamental concept in graph theory, and the chromatic number is a key parameter that quantifies the coloring properties of a graph. Let’s go into the introductory aspects of the chromatic number.
Graph coloring refers to the problem of coloring vertices of a graph in such a way that no two adjacent vertices have the same color. This is also called the vertex coloring problem. If coloring is done using at most m colors, it is called m-coloring.
Table of Content
- What is Chromatic Number?
- Chromatic Number of Cyclic Graph:
- Chromatic Number of Complete Graph:
- Chromatic Number of Bipartite Graph:
- Chromatic Number of Star Graph:
- Chromatic Number of Wheel Graph:
- Chromatic Number of Planar Graph:
- Properites of Chromatic Number:
- Importance of Chromatic Number in Graph Theory:
- Algorithm to Find Chromatic Numbers
- Choosing the right algorithm for finding chromatic number depends on the specific graph:
- Relation between chromatic number and chromatic polynomial
- Analogy:
- Related Articles:
Contact Us