Greedy Coloring

Graph coloring is a computational problem where the objective is to assign colors to the vertices of a graph such that no two adjacent vertices (nodes connected by an edge) share the same color. The Greedy Coloring algorithm is a straightforward and fast approach to solving this problem by assigning the first available color to each node chronologically.

         Real-World Application:
        Graph coloring is heavily used in scheduling (making sure no two overlapping exams are
        scheduled in the same room), Sudoku puzzles, and map coloring. While greedy coloring doesn't
        guarantee the absolute minimum number of colors mathematically possible, it is extremely
        fast and provides a "good enough" approximation for large networks.
      

The Algorithm Principle

The logic follows a simple "first come, first served" strategy:

Colors are represented by integers (Color 0, Color 1, Color 2...).
Iterate through all the nodes in the graph one by one.
For the current node, look at all its immediate neighbors and note which colors they are already using.
Assign the smallest integer color that is not currently being used by any of its neighbors.
Move to the next uncolored node and repeat.

Algorithm Walkthrough

In our implementation below, we gather all nodes in the graph and color them sequentially, ensuring we visually apply distinct colors from a predefined palette.

def greedy_coloring():
    PALETTE = ["#EF4444", "#3B82F6", "#10B981", "#F59E0B", "#8B5CF6"]
    
    all_nodes = get_all_nodes() 
    colors = {}
    
    if len(all_nodes) > 0:
        visit(all_nodes[0], "Starting Global Greedy Coloring...")
    
    for node in all_nodes:
        select(node)
        
        # 1. Gather all neighbors
        undirected_neighbors = set(neighbors(node))
        for other_node in all_nodes:
            if node in neighbors(other_node):
                undirected_neighbors.add(other_node)
                
        # 2. Check colors used by neighbors
        used_colors = set()
        for neighbor in undirected_neighbors:
            if neighbor in colors:
                used_colors.add(colors[neighbor])
                
        # 3. Find the lowest available color integer
        color_index = 0
        while color_index in used_colors:
            color_index += 1
            
        # 4. Assign the color and display it
        colors[node] = color_index
        hex_color = PALETTE[color_index % len(PALETTE)]
        
        color_node(node, hex_color, f"Node {node} is assigned to Color {color_index}")

greedy_coloring()

Complexity

The performance is excellent for general-purpose applications, though it varies slightly depending on how the graph is structured.

Metric	Complexity	Explanation
Time Complexity	$O(V + E)$	Where $V$ is the number of vertices and $E$ is the number of edges. We visit every vertex once, and for each vertex, we check its adjacent edges. Finding the lowest available color takes linear time proportional to the number of neighbors.
Space Complexity	$O(V)$	We only need to store the assigned color for each of the $V$ vertices in a dictionary or array.