Graph Coloring

Overview

Graph coloring assigns labels (colors) to graph elements subject to constraints that adjacent elements receive different colors. The vertex coloring problem assigns colors to vertices such that no two adjacent vertices share the same color. The chromatic number represents the minimum number of colors needed to color a graph following these constraints.

The problem originates from the Four Color Theorem, which states that any planar map can be colored with four colors such that no adjacent regions share the same color. Graph coloring extends beyond cartography into scheduling, register allocation in compilers, frequency assignment in wireless networks, and pattern matching.

# Simple graph representation showing adjacency
graph = {
  'A' => ['B', 'C'],
  'B' => ['A', 'C', 'D'],
  'C' => ['A', 'B', 'D'],
  'D' => ['B', 'C']
}

# A valid 3-coloring of this graph
coloring = {
  'A' => 'red',
  'B' => 'blue',
  'C' => 'green',
  'D' => 'red'
}

The vertex coloring problem belongs to the class of NP-complete problems, meaning no known polynomial-time algorithm exists for finding optimal colorings of arbitrary graphs. However, specific graph types (bipartite graphs, trees, interval graphs) admit efficient coloring algorithms. Greedy approaches produce approximate solutions with bounded performance guarantees.

Key Principles

Graph coloring operates on undirected graphs G = (V, E) where V represents vertices and E represents edges connecting vertex pairs. A k-coloring assigns one of k colors to each vertex such that vertices connected by an edge receive distinct colors. The chromatic number χ(G) denotes the smallest k for which a valid k-coloring exists.

Several graph properties determine coloring complexity. The maximum degree Δ(G) provides an upper bound: any graph can be colored with Δ(G) + 1 colors using a greedy algorithm. Bipartite graphs have chromatic number 2, while complete graphs on n vertices require n colors. Planar graphs require at most four colors, though determining the chromatic number for a specific planar graph remains NP-complete.

# Graph with known chromatic properties
class Graph
  attr_reader :vertices, :edges
  
  def initialize
    @vertices = []
    @edges = {}
  end
  
  def add_vertex(vertex)
    @vertices << vertex
    @edges[vertex] = []
  end
  
  def add_edge(v1, v2)
    @edges[v1] << v2
    @edges[v2] << v1
  end
  
  def degree(vertex)
    @edges[vertex].length
  end
  
  def max_degree
    @vertices.map { |v| degree(v) }.max
  end
end

Proper coloring ensures that the coloring function maps each vertex to a color while satisfying constraints. An improper coloring violates the adjacency constraint, creating conflicts where adjacent vertices share colors. The coloring problem decomposes into finding independent sets: vertices receiving the same color form an independent set with no internal edges.

Graph coloring relates to other graph problems through reductions. The clique problem connects to coloring through complement graphs: a k-clique in G becomes an independent set requiring k colors in the complement. The satisfiability problem reduces to graph coloring, establishing NP-completeness. Conversely, coloring reduces to SAT, enabling SAT solver application to coloring problems.

# Checking coloring validity
def valid_coloring?(graph, coloring)
  graph.vertices.all? do |vertex|
    neighbors = graph.edges[vertex]
    neighbors.none? { |neighbor| coloring[vertex] == coloring[neighbor] }
  end
end

# Example validation
graph = Graph.new
['A', 'B', 'C'].each { |v| graph.add_vertex(v) }
graph.add_edge('A', 'B')
graph.add_edge('B', 'C')

coloring = { 'A' => 1, 'B' => 2, 'C' => 1 }
valid_coloring?(graph, coloring)  # => true

The greedy coloring strategy processes vertices in sequence, assigning each vertex the smallest available color not used by its neighbors. The vertex ordering significantly impacts the number of colors used. Worst-case vertex orderings force greedy algorithms to use Δ(G) + 1 colors, while optimal orderings may achieve χ(G) colors.

Ruby Implementation

Ruby graph coloring implementations typically represent graphs as adjacency lists using hashes. This representation provides efficient neighbor lookups during color assignment and constraint checking.

class GraphColoring
  attr_reader :graph, :coloring, :num_colors
  
  def initialize(graph)
    @graph = graph
    @coloring = {}
    @num_colors = 0
  end
  
  def greedy_color(vertex_order = nil)
    order = vertex_order || @graph.vertices
    
    order.each do |vertex|
      used_colors = @graph.edges[vertex].map { |neighbor| @coloring[neighbor] }.compact.to_set
      
      color = (1..Float::INFINITY).lazy.find { |c| !used_colors.include?(c) }
      @coloring[vertex] = color
      @num_colors = [@num_colors, color].max
    end
    
    @coloring
  end
  
  def color_count
    @num_colors
  end
end

# Usage example
graph = Graph.new
vertices = ['A', 'B', 'C', 'D', 'E']
vertices.each { |v| graph.add_vertex(v) }
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')
graph.add_edge('C', 'D')
graph.add_edge('D', 'E')

coloring = GraphColoring.new(graph)
coloring.greedy_color
# => {"A"=>1, "B"=>2, "C"=>2, "D"=>1, "E"=>2}

Welsh-Powell ordering improves greedy coloring by processing vertices in descending degree order. Vertices with higher degrees receive colors first, reducing the total color count for many graph types.

class GraphColoring
  def welsh_powell_order
    @graph.vertices.sort_by { |v| -@graph.degree(v) }
  end
  
  def welsh_powell_coloring
    order = welsh_powell_order
    greedy_color(order)
  end
end

# Comparison of orderings
coloring1 = GraphColoring.new(graph)
coloring1.greedy_color  # Arbitrary order

coloring2 = GraphColoring.new(graph)
coloring2.welsh_powell_coloring  # Degree-based order

puts "Arbitrary ordering: #{coloring1.color_count} colors"
puts "Welsh-Powell ordering: #{coloring2.color_count} colors"

Backtracking algorithms explore the solution space systematically, finding optimal colorings at the cost of exponential worst-case complexity. The algorithm tries assigning each color to a vertex, recursively coloring remaining vertices, and backtracking when conflicts occur.

class BacktrackingColoring
  def initialize(graph, max_colors)
    @graph = graph
    @max_colors = max_colors
    @coloring = {}
    @solution = nil
  end
  
  def solve
    return @solution if @solution
    
    if backtrack(@graph.vertices, 0)
      @solution = @coloring.dup
    end
    
    @solution
  end
  
  private
  
  def backtrack(vertices, index)
    return true if index == vertices.length
    
    vertex = vertices[index]
    
    (1..@max_colors).each do |color|
      if safe_color?(vertex, color)
        @coloring[vertex] = color
        return true if backtrack(vertices, index + 1)
        @coloring.delete(vertex)
      end
    end
    
    false
  end
  
  def safe_color?(vertex, color)
    @graph.edges[vertex].none? { |neighbor| @coloring[neighbor] == color }
  end
end

# Finding minimum colors
def find_chromatic_number(graph)
  (1..graph.vertices.length).each do |k|
    solver = BacktrackingColoring.new(graph, k)
    return k if solver.solve
  end
end

Ruby's flexibility enables domain-specific coloring implementations. Register allocation in compilers maps variables to registers, where interference graphs represent conflicting live ranges. Scheduling problems model incompatible activities as adjacent vertices.

# Register allocation example
class RegisterAllocator
  def initialize(interference_graph, num_registers)
    @graph = interference_graph
    @num_registers = num_registers
  end
  
  def allocate
    coloring = GraphColoring.new(@graph)
    coloring.welsh_powell_coloring
    
    if coloring.color_count <= @num_registers
      map_colors_to_registers(coloring.coloring)
    else
      spill_variables(coloring)
    end
  end
  
  private
  
  def map_colors_to_registers(coloring)
    register_names = ('r0'..'r31').to_a
    coloring.transform_values { |color| register_names[color - 1] }
  end
  
  def spill_variables(coloring)
    # Variables requiring more colors than available registers
    # must be spilled to memory
    threshold = @num_registers
    spilled = coloring.coloring.select { |_, color| color > threshold }.keys
    { spilled: spilled, allocated: coloring.coloring.reject { |k, _| spilled.include?(k) } }
  end
end

Implementation Approaches

Multiple algorithmic strategies address graph coloring with different trade-offs between solution quality and computational cost. The approach selection depends on graph characteristics, required solution optimality, and available computation time.

Greedy sequential coloring processes vertices one at a time, assigning the minimum available color. The algorithm requires O(V + E) time but produces solutions potentially far from optimal. The performance guarantee states that greedy coloring uses at most Δ(G) + 1 colors, where Δ(G) represents the maximum vertex degree.

# Basic greedy implementation with ordering parameter
def greedy_coloring(graph, ordering_strategy)
  vertices = case ordering_strategy
             when :natural then graph.vertices
             when :degree then graph.vertices.sort_by { |v| -graph.degree(v) }
             when :random then graph.vertices.shuffle
             end
  
  coloring = {}
  
  vertices.each do |vertex|
    neighbor_colors = graph.edges[vertex].filter_map { |n| coloring[n] }.to_set
    color = (1..).find { |c| !neighbor_colors.include?(c) }
    coloring[vertex] = color
  end
  
  coloring
end

DSATUR (Degree of Saturation) represents a dynamic ordering strategy that selects vertices based on the number of distinct colors used by their neighbors. Vertices with higher saturation degrees receive colors first, often producing better results than static orderings.

class DSaturColoring
  def initialize(graph)
    @graph = graph
    @coloring = {}
    @saturation = Hash.new(0)
  end
  
  def color
    uncolored = @graph.vertices.to_set
    
    until uncolored.empty?
      vertex = select_vertex(uncolored)
      assign_color(vertex)
      uncolored.delete(vertex)
      update_saturation(vertex)
    end
    
    @coloring
  end
  
  private
  
  def select_vertex(uncolored)
    uncolored.max_by do |v|
      [@saturation[v], @graph.degree(v), -@graph.vertices.index(v)]
    end
  end
  
  def assign_color(vertex)
    used_colors = @graph.edges[vertex].filter_map { |n| @coloring[n] }.to_set
    @coloring[vertex] = (1..).find { |c| !used_colors.include?(c) }
  end
  
  def update_saturation(vertex)
    @graph.edges[vertex].each do |neighbor|
      next if @coloring.key?(neighbor)
      
      neighbor_colors = @graph.edges[neighbor].filter_map { |n| @coloring[n] }
      @saturation[neighbor] = neighbor_colors.uniq.length
    end
  end
end

Backtracking exhaustively searches the solution space, guaranteeing optimal solutions for small graphs. The algorithm explores color assignments recursively, pruning branches when conflicts occur. Pruning strategies significantly impact performance: forward checking eliminates values violating constraints before assignment.

Branch-and-bound extends backtracking with bounds on the objective function. The algorithm maintains the best solution found so far and prunes branches that cannot improve upon it. For coloring, the bound represents a lower estimate of colors needed to complete the current partial coloring.

class BranchAndBoundColoring
  def initialize(graph)
    @graph = graph
    @best_coloring = nil
    @best_colors = Float::INFINITY
  end
  
  def solve
    initial_bound = greedy_upper_bound
    branch(@graph.vertices, {}, 0, initial_bound)
    @best_coloring
  end
  
  private
  
  def branch(vertices, partial_coloring, index, upper_bound)
    if index == vertices.length
      color_count = partial_coloring.values.max
      if color_count < @best_colors
        @best_colors = color_count
        @best_coloring = partial_coloring.dup
      end
      return
    end
    
    vertex = vertices[index]
    lower_bound = compute_lower_bound(partial_coloring, vertices[index..])
    
    return if lower_bound >= @best_colors
    
    (1..upper_bound).each do |color|
      if color_safe?(vertex, color, partial_coloring)
        partial_coloring[vertex] = color
        branch(vertices, partial_coloring, index + 1, upper_bound)
        partial_coloring.delete(vertex)
      end
    end
  end
  
  def compute_lower_bound(partial_coloring, remaining_vertices)
    used_colors = partial_coloring.values.max || 0
    max_clique_size = estimate_max_clique(remaining_vertices)
    [used_colors, max_clique_size].max
  end
  
  def estimate_max_clique(vertices)
    # Simple greedy clique estimation
    return 0 if vertices.empty?
    
    clique = [vertices.first]
    vertices[1..].each do |v|
      if clique.all? { |c| @graph.edges[v].include?(c) }
        clique << v
      end
    end
    clique.length
  end
  
  def greedy_upper_bound
    GraphColoring.new(@graph).welsh_powell_coloring.color_count
  end
  
  def color_safe?(vertex, color, coloring)
    @graph.edges[vertex].none? { |neighbor| coloring[neighbor] == color }
  end
end

Integer programming formulations encode coloring as constraint satisfaction problems solvable by generic solvers. Variables represent vertex-color assignments, with constraints ensuring adjacent vertices receive different colors. Modern solvers handle moderate-sized instances effectively.

Hybrid approaches combine heuristics with exact methods. Iterative greedy algorithms repeatedly apply randomized greedy coloring, retaining the best solution. Simulated annealing and genetic algorithms explore the solution space probabilistically, escaping local optima.

Practical Examples

Graph coloring solves scheduling problems where activities cannot overlap. The exam scheduling scenario assigns time slots to exams such that students with multiple exams receive adequate separation.

class ExamScheduler
  def initialize
    @exams = []
    @conflicts = Hash.new { |h, k| h[k] = [] }
  end
  
  def add_exam(exam)
    @exams << exam
  end
  
  def add_conflict(exam1, exam2)
    @conflicts[exam1] << exam2
    @conflicts[exam2] << exam1
  end
  
  def schedule(time_slots)
    graph = build_conflict_graph
    coloring = GraphColoring.new(graph)
    result = coloring.welsh_powell_coloring
    
    if coloring.color_count <= time_slots.length
      map_to_schedule(result, time_slots)
    else
      { error: "Need #{coloring.color_count} time slots, only #{time_slots.length} available" }
    end
  end
  
  private
  
  def build_conflict_graph
    graph = Graph.new
    @exams.each { |exam| graph.add_vertex(exam) }
    @conflicts.each do |exam, conflicts|
      conflicts.each { |conflict| graph.add_edge(exam, conflict) }
    end
    graph
  end
  
  def map_to_schedule(coloring, time_slots)
    coloring.transform_values { |color| time_slots[color - 1] }
  end
end

# Usage example
scheduler = ExamScheduler.new
%w[Math Physics Chemistry Biology English History].each { |exam| scheduler.add_exam(exam) }

# Students taking multiple courses create conflicts
scheduler.add_conflict('Math', 'Physics')
scheduler.add_conflict('Math', 'Chemistry')
scheduler.add_conflict('Physics', 'Biology')
scheduler.add_conflict('Chemistry', 'Biology')
scheduler.add_conflict('English', 'History')

time_slots = ['Monday 9am', 'Monday 2pm', 'Tuesday 9am']
schedule = scheduler.schedule(time_slots)
# => {"Math"=>"Monday 9am", "Physics"=>"Monday 2pm", "Chemistry"=>"Tuesday 9am", ...}

Map coloring demonstrates classical graph coloring applications. Regions sharing borders cannot receive identical colors, requiring minimum colors to distinguish all regions.

class MapColoring
  def initialize
    @regions = {}
  end
  
  def add_region(name, borders)
    @regions[name] = borders
  end
  
  def color_map
    graph = build_region_graph
    coloring = DSaturColoring.new(graph)
    result = coloring.color
    
    color_names = %w[Red Blue Green Yellow Orange Purple]
    result.transform_values { |num| color_names[num - 1] }
  end
  
  private
  
  def build_region_graph
    graph = Graph.new
    @regions.keys.each { |region| graph.add_vertex(region) }
    @regions.each do |region, borders|
      borders.each { |border| graph.add_edge(region, border) if @regions.key?(border) }
    end
    graph
  end
end

# US state borders example (partial)
map = MapColoring.new
map.add_region('California', ['Oregon', 'Nevada', 'Arizona'])
map.add_region('Oregon', ['California', 'Nevada', 'Idaho', 'Washington'])
map.add_region('Nevada', ['California', 'Oregon', 'Idaho', 'Utah', 'Arizona'])
map.add_region('Arizona', ['California', 'Nevada', 'Utah', 'New Mexico'])
map.add_region('Idaho', ['Oregon', 'Nevada', 'Utah', 'Wyoming', 'Montana', 'Washington'])

colors = map.color_map
# => {"California"=>"Red", "Oregon"=>"Blue", "Nevada"=>"Green", ...}

Register allocation in compilers assigns variables to limited processor registers. Variables with overlapping live ranges cannot share registers, creating an interference graph colored with available registers.

class CompilerRegisterAllocation
  def initialize(num_registers)
    @num_registers = num_registers
    @live_ranges = {}
  end
  
  def add_variable(var, start_line, end_line)
    @live_ranges[var] = (start_line..end_line)
  end
  
  def allocate
    interference = build_interference_graph
    coloring = GraphColoring.new(interference)
    result = coloring.welsh_powell_coloring
    
    if coloring.color_count <= @num_registers
      assign_registers(result)
    else
      handle_spilling(result, coloring.color_count)
    end
  end
  
  private
  
  def build_interference_graph
    graph = Graph.new
    @live_ranges.keys.each { |var| graph.add_vertex(var) }
    
    @live_ranges.keys.combination(2) do |var1, var2|
      range1, range2 = @live_ranges[var1], @live_ranges[var2]
      graph.add_edge(var1, var2) if ranges_overlap?(range1, range2)
    end
    
    graph
  end
  
  def ranges_overlap?(range1, range2)
    range1.cover?(range2.first) || range2.cover?(range1.first)
  end
  
  def assign_registers(coloring)
    registers = (0...@num_registers).map { |i| "R#{i}" }
    coloring.transform_values { |color| registers[color - 1] }
  end
  
  def handle_spilling(coloring, needed_colors)
    registers = (0...@num_registers).map { |i| "R#{i}" }
    allocation = {}
    spilled = []
    
    coloring.each do |var, color|
      if color <= @num_registers
        allocation[var] = registers[color - 1]
      else
        spilled << var
        allocation[var] = 'MEMORY'
      end
    end
    
    { allocation: allocation, spilled: spilled }
  end
end

# Example usage
allocator = CompilerRegisterAllocation.new(4)
allocator.add_variable('a', 1, 5)
allocator.add_variable('b', 2, 7)
allocator.add_variable('c', 3, 6)
allocator.add_variable('d', 5, 8)
allocator.add_variable('e', 6, 9)

result = allocator.allocate
# => {"a"=>"R0", "b"=>"R1", "c"=>"R2", "d"=>"R0", "e"=>"R1"}

Frequency assignment in wireless networks allocates channels to transmitters, preventing interference between nearby stations. The constraint graph connects transmitters within interference range, requiring different frequencies.

class FrequencyAssignment
  def initialize(transmitters, interference_distance)
    @transmitters = transmitters  # Hash of transmitter => [x, y] coordinates
    @interference_distance = interference_distance
    @channels = []
  end
  
  def assign_frequencies(available_channels)
    @channels = available_channels
    interference_graph = build_interference_graph
    
    coloring = DSaturColoring.new(interference_graph)
    channel_assignment = coloring.color
    
    map_to_frequencies(channel_assignment)
  end
  
  private
  
  def build_interference_graph
    graph = Graph.new
    @transmitters.keys.each { |t| graph.add_vertex(t) }
    
    @transmitters.keys.combination(2) do |t1, t2|
      distance = calculate_distance(@transmitters[t1], @transmitters[t2])
      graph.add_edge(t1, t2) if distance <= @interference_distance
    end
    
    graph
  end
  
  def calculate_distance(point1, point2)
    Math.sqrt((point1[0] - point2[0])**2 + (point1[1] - point2[1])**2)
  end
  
  def map_to_frequencies(coloring)
    coloring.transform_values { |color| @channels[color - 1] }
  end
end

# Example network
transmitters = {
  'Tower1' => [0, 0],
  'Tower2' => [3, 4],
  'Tower3' => [6, 0],
  'Tower4' => [3, -4],
  'Tower5' => [10, 5]
}

assigner = FrequencyAssignment.new(transmitters, 6.0)
channels = ['Channel A', 'Channel B', 'Channel C', 'Channel D']
assignment = assigner.assign_frequencies(channels)
# => {"Tower1"=>"Channel A", "Tower2"=>"Channel B", "Tower3"=>"Channel A", ...}

Performance Considerations

Graph coloring complexity depends on both graph structure and solution quality requirements. Computing the chromatic number remains NP-complete, while finding any valid coloring (potentially suboptimal) admits polynomial-time solutions through greedy algorithms.

Greedy coloring achieves O(V + E) time complexity by processing each vertex once and checking neighbor colors. The Welsh-Powell variant adds O(V log V) sorting overhead but often reduces total colors used. DSATUR increases complexity to O(V²) due to dynamic vertex selection based on saturation degrees.

require 'benchmark'

def benchmark_coloring_methods(graph)
  Benchmark.bm(20) do |x|
    x.report('Greedy (natural):') do
      1000.times { GraphColoring.new(graph).greedy_color }
    end
    
    x.report('Welsh-Powell:') do
      1000.times { GraphColoring.new(graph).welsh_powell_coloring }
    end
    
    x.report('DSATUR:') do
      1000.times { DSaturColoring.new(graph).color }
    end
  end
end

# Performance varies with graph density and structure
sparse_graph = generate_random_graph(100, 0.05)
dense_graph = generate_random_graph(100, 0.5)

puts "Sparse graph (5% density):"
benchmark_coloring_methods(sparse_graph)

puts "\nDense graph (50% density):"
benchmark_coloring_methods(dense_graph)

Backtracking algorithms exhibit exponential worst-case complexity O(k^V) where k represents the number of colors. Practical performance depends heavily on graph structure and pruning effectiveness. Graphs with large independent sets or low chromatic numbers prune search trees more aggressively.

Memory consumption scales with graph representation choice. Adjacency matrices require O(V²) space but provide O(1) edge lookup. Adjacency lists use O(V + E) space with O(degree(v)) neighbor access. For sparse graphs (E << V²), adjacency lists conserve memory significantly.

class GraphRepresentationComparison
  def self.memory_analysis(num_vertices, edge_density)
    num_edges = (num_vertices * (num_vertices - 1) / 2 * edge_density).to_i
    
    # Adjacency matrix: V x V booleans
    matrix_bytes = num_vertices * num_vertices
    
    # Adjacency list: V vertex entries + 2E edge references
    list_bytes = num_vertices * 40 + num_edges * 2 * 8  # Approximate Ruby object sizes
    
    {
      vertices: num_vertices,
      edges: num_edges,
      density: edge_density,
      matrix_memory_kb: matrix_bytes / 1024.0,
      list_memory_kb: list_bytes / 1024.0,
      ratio: matrix_bytes.to_f / list_bytes
    }
  end
end

# Comparison across different densities
[0.01, 0.1, 0.5, 0.9].each do |density|
  stats = GraphRepresentationComparison.memory_analysis(1000, density)
  puts "Density #{density}: Matrix=#{stats[:matrix_memory_kb].round(2)}KB, " \
       "List=#{stats[:list_memory_kb].round(2)}KB, Ratio=#{stats[:ratio].round(2)}"
end

Vertex ordering dramatically impacts greedy algorithm performance. Random orderings produce unpredictable results, while degree-based orderings provide consistent improvements. The largest-degree-first heuristic (Welsh-Powell) guarantees using at most max(d₁, d₂, ..., dₙ) + 1 colors where dᵢ represents vertex degrees in non-increasing order.

Parallel coloring algorithms partition the graph and color independent vertex sets concurrently. Jones-Plassmann algorithm assigns random priorities to vertices and colors maximal independent sets in parallel phases. The approach achieves speedup on multi-core systems but may use more colors than sequential algorithms.

require 'concurrent'

class ParallelColoring
  def initialize(graph, thread_pool_size = 4)
    @graph = graph
    @pool = Concurrent::FixedThreadPool.new(thread_pool_size)
    @coloring = Concurrent::Hash.new
  end
  
  def color
    uncolored = @graph.vertices.to_set
    color_num = 1
    
    until uncolored.empty?
      independent_set = find_maximal_independent_set(uncolored)
      
      # Color independent set in parallel
      futures = independent_set.map do |vertex|
        Concurrent::Future.execute(executor: @pool) do
          @coloring[vertex] = color_num
        end
      end
      
      futures.each(&:wait)
      uncolored -= independent_set
      color_num += 1
    end
    
    @pool.shutdown
    @pool.wait_for_termination
    
    @coloring.to_h
  end
  
  private
  
  def find_maximal_independent_set(vertices)
    independent = Set.new
    vertices = vertices.to_a.shuffle
    
    vertices.each do |v|
      neighbors = @graph.edges[v].to_set
      independent << v unless independent.any? { |i| neighbors.include?(i) }
    end
    
    independent
  end
end

Cache locality affects performance for large graphs. Breadth-first vertex orderings improve cache hits by coloring nearby vertices in sequence. Recursive backtracking algorithms benefit from tail-call optimization where available, though Ruby does not optimize tail calls by default.

Graph preprocessing reduces problem size through transformations. Identifying and removing simplicial vertices (vertices whose neighbors form a clique) decreases graph size while preserving chromatic number. Clique detection eliminates vertices that must receive distinct colors.

Common Patterns

Independent set coloring partitions vertices into color classes representing independent sets. Each iteration identifies a maximal independent set, assigns a new color to all vertices in the set, and removes them from consideration. The process continues until all vertices receive colors.

class IndependentSetColoring
  def initialize(graph)
    @graph = graph
  end
  
  def color
    remaining = @graph.vertices.to_set
    coloring = {}
    color = 1
    
    until remaining.empty?
      independent_set = find_independent_set(remaining)
      independent_set.each { |v| coloring[v] = color }
      remaining -= independent_set
      color += 1
    end
    
    coloring
  end
  
  private
  
  def find_independent_set(vertices)
    independent = Set.new
    available = vertices.dup
    
    until available.empty?
      vertex = available.first
      independent << vertex
      
      # Remove vertex and its neighbors
      available.delete(vertex)
      @graph.edges[vertex].each { |neighbor| available.delete(neighbor) }
    end
    
    independent
  end
end

Smallest-last ordering processes vertices in reverse order of removal when repeatedly removing minimum-degree vertices. This degeneracy-based ordering often outperforms simple degree-based approaches, particularly for graphs with small degeneracy.

class SmallestLastColoring
  def initialize(graph)
    @graph = graph
  end
  
  def color
    ordering = compute_smallest_last_order
    coloring = {}
    
    ordering.each do |vertex|
      neighbor_colors = @graph.edges[vertex].filter_map { |n| coloring[n] }.to_set
      coloring[vertex] = (1..).find { |c| !neighbor_colors.include?(c) }
    end
    
    coloring
  end
  
  private
  
  def compute_smallest_last_order
    remaining = @graph.vertices.to_set
    order = []
    degrees = @graph.vertices.to_h { |v| [v, @graph.degree(v)] }
    
    until remaining.empty?
      # Select minimum degree vertex from remaining
      vertex = remaining.min_by { |v| degrees[v] }
      order.unshift(vertex)
      remaining.delete(vertex)
      
      # Update neighbor degrees
      @graph.edges[vertex].each do |neighbor|
        degrees[neighbor] -= 1 if remaining.include?(neighbor)
      end
    end
    
    order
  end
end

Iterated greedy improves solutions through repeated randomized coloring. The algorithm applies greedy coloring with random vertex orderings multiple times, retaining the best solution. This pattern balances solution quality and computation time effectively.

class IteratedGreedyColoring
  def initialize(graph, iterations = 100)
    @graph = graph
    @iterations = iterations
  end
  
  def color
    best_coloring = nil
    best_colors = Float::INFINITY
    
    @iterations.times do
      ordering = @graph.vertices.shuffle
      coloring = greedy_with_order(ordering)
      colors_used = coloring.values.max
      
      if colors_used < best_colors
        best_colors = colors_used
        best_coloring = coloring
      end
    end
    
    best_coloring
  end
  
  private
  
  def greedy_with_order(ordering)
    coloring = {}
    
    ordering.each do |vertex|
      used = @graph.edges[vertex].filter_map { |n| coloring[n] }.to_set
      coloring[vertex] = (1..).find { |c| !used.include?(c) }
    end
    
    coloring
  end
end

Tabu search maintains a memory of recently explored solutions, preventing cycles in local search. The algorithm iteratively modifies the current coloring by recoloring vertices, avoiding recently used color-vertex combinations. This pattern escapes local optima more effectively than simple hill climbing.

Conflict-based recoloring targets vertices involved in color conflicts. When a partial k-coloring contains conflicts, the algorithm selects conflicting vertices and reassigns their colors. Kempe chains (alternating color sequences) enable conflict-free color swaps.

class KempeChainColoring
  def initialize(graph)
    @graph = graph
    @coloring = {}
  end
  
  def improve_coloring(initial_coloring)
    @coloring = initial_coloring.dup
    max_color = @coloring.values.max
    
    # Try to reduce colors used
    (1..max_color).reverse_each do |target_color|
      vertices_with_color = @coloring.select { |_, c| c == target_color }.keys
      
      vertices_with_color.each do |vertex|
        (1...target_color).each do |new_color|
          if can_swap_via_kempe_chain?(vertex, target_color, new_color)
            perform_kempe_swap(vertex, target_color, new_color)
            break
          end
        end
      end
    end
    
    @coloring
  end
  
  private
  
  def can_swap_via_kempe_chain?(start_vertex, color1, color2)
    # Build component of vertices with color1 or color2
    component = find_kempe_component(start_vertex, color1, color2)
    
    # Check if swapping colors in component creates conflicts
    component.none? do |v|
      new_color = @coloring[v] == color1 ? color2 : color1
      @graph.edges[v].any? { |n| !component.include?(n) && @coloring[n] == new_color }
    end
  end
  
  def find_kempe_component(start, color1, color2)
    component = Set.new([start])
    queue = [start]
    
    until queue.empty?
      vertex = queue.shift
      
      @graph.edges[vertex].each do |neighbor|
        next if component.include?(neighbor)
        next unless [color1, color2].include?(@coloring[neighbor])
        
        component << neighbor
        queue << neighbor
      end
    end
    
    component
  end
  
  def perform_kempe_swap(start_vertex, color1, color2)
    component = find_kempe_component(start_vertex, color1, color2)
    
    component.each do |vertex|
      @coloring[vertex] = @coloring[vertex] == color1 ? color2 : color1
    end
  end
end

Clique-based bounds establish lower limits on chromatic number. Any clique (complete subgraph) requires |clique| distinct colors, providing a chromatic lower bound. Algorithms detecting maximum cliques tighten this bound, improving branch-and-bound pruning.

Reference

Complexity Classes

Algorithm Comparison

Graph Properties

Ruby Method Reference

Color Bound Formulas

Common Graph Types

Application Domains

Performance Optimization Strategies