Yog.Property.Coloring (YogEx v0.97.0)

Graph coloring algorithms for finding valid colorings and estimating the chromatic number.

Graph coloring assigns colors to vertices such that no two adjacent vertices share the same color. The minimum number of colors needed is called the chromatic number χ(G).

Algorithms

Problem	Algorithm	Function	Complexity
Greedy coloring	Welsh-Powell	`coloring_greedy/1`	O(V²)
DSatur heuristic	Degree of Saturation	`coloring_dsatur/1`	O(V²)
Exact coloring	Backtracking with pruning	`coloring_exact/2`	O(k^V) worst case

Key Concepts

Proper Coloring: No adjacent vertices share the same color
Chromatic Number χ(G): Minimum number of colors needed
Upper Bound: Any valid coloring gives an upper bound on χ(G)
Greedy Coloring: Fast but not optimal; bound depends on vertex ordering
DSatur: Usually produces better colorings than simple greedy
Exact: Finds optimal coloring via backtracking (practical for V < 30)

Use Cases

Scheduling: Conflicting tasks get different time slots
Register allocation: Variables that overlap need different registers
Map coloring: Adjacent regions get different colors
Frequency assignment: Nearby transmitters use different frequencies
Exam scheduling: Courses with shared students need different times

Examples

iex> alias Yog.Property.Coloring
iex> graph = Yog.Generator.Classic.complete(3)
iex> {upper, colors} = Coloring.coloring_greedy(graph)
iex> upper
3
iex> colors
%{0 => 1, 1 => 2, 2 => 3}
iex> {:ok, chi, _exact_colors} = Coloring.coloring_exact(graph)
iex> chi
3

References

Summary

Types

coloring_result()

A coloring result consisting of the chromatic upper bound and a node-to-color map. Colors are positive integers starting from 1.

exact_result()

Result of exact coloring: either an optimal solution or a timeout with the best found.

Functions

coloring_dsatur(graph)

DSatur heuristic for graph coloring.

coloring_exact(graph, timeout_ms \\ 5000)

Exact graph coloring using backtracking with pruning and an optional timeout.

coloring_greedy(graph)

Greedy graph coloring using Welsh-Powell ordering.

Types

coloring_result()

@type coloring_result() ::
  {non_neg_integer(), %{required(Yog.node_id()) => pos_integer()}}

A coloring result consisting of the chromatic upper bound and a node-to-color map. Colors are positive integers starting from 1.

exact_result()

@type exact_result() ::
  {:ok, pos_integer(), %{required(Yog.node_id()) => pos_integer()}}
  | {:timeout, coloring_result()}

Result of exact coloring: either an optimal solution or a timeout with the best found.

Functions

coloring_dsatur(graph)

@spec coloring_dsatur(Yog.graph()) :: coloring_result()

DSatur heuristic for graph coloring.

At each step, the uncolored node with the highest "saturation degree" (number of distinct colors among its colored neighbors) is chosen. Ties are broken by total degree. This usually produces better colorings than simple greedy ordering.

Examples

iex> graph = Yog.Generator.Classic.cycle(5)
iex> {upper, _colors} = Yog.Property.Coloring.coloring_dsatur(graph)
iex> upper == 3
true

Time Complexity

O(V²) for this implementation.

coloring_exact(graph, timeout_ms \\ 5000)

@spec coloring_exact(Yog.graph(), pos_integer()) :: exact_result()

Exact graph coloring using backtracking with pruning and an optional timeout.

Tries to find the optimal (minimum) number of colors. For small graphs (roughly V < 30), this is usually fast enough. A timeout prevents the algorithm from hanging on larger or pathological instances.

Returns {:ok, chromatic_number, coloring} on success, or {:timeout, best_result} if the timeout is reached, where best_result is the best valid coloring found so far.

Examples

iex> graph = Yog.Generator.Classic.complete(4)
iex> {:ok, chi, _colors} = Yog.Property.Coloring.coloring_exact(graph)
iex> chi == 4
true

iex> bipartite = Yog.Generator.Classic.complete_bipartite(3, 3)
iex> {:ok, chi, _b_colors} = Yog.Property.Coloring.coloring_exact(bipartite)
iex> chi == 2
true

Time Complexity

Exponential in the worst case. Intended for small graphs only.

coloring_greedy(graph)

@spec coloring_greedy(Yog.graph()) :: coloring_result()

Greedy graph coloring using Welsh-Powell ordering.

Nodes are sorted by degree in descending order, then each node is assigned the smallest available color not used by any of its already-colored neighbors.

Examples

iex> graph = Yog.Generator.Classic.complete(3)
iex> {upper, colors} = Yog.Property.Coloring.coloring_greedy(graph)
iex> upper == 3
true
iex> colors[0] != colors[1]
true

iex> empty = Yog.Generator.Classic.empty(3)
iex> {upper, _colors} = Yog.Property.Coloring.coloring_greedy(empty)
iex> upper == 1
true

Time Complexity

O(V²) in the worst case; O(V log V + E) with more efficient structures.