# `Yog.Property.Coloring`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.97.0/lib/yog/property/coloring.ex#L1)

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](https://en.wikipedia.org/wiki/Graph_coloring#Greedy_coloring) | `coloring_greedy/1` | O(V²) |
| DSatur heuristic | [Degree of Saturation](https://en.wikipedia.org/wiki/DSatur) | `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

- [Wikipedia: Graph Coloring](https://en.wikipedia.org/wiki/Graph_coloring)
- [Wikipedia: DSatur](https://en.wikipedia.org/wiki/DSatur)
- [CP-Algorithms: Graph Coloring](https://cp-algorithms.com/graph/bipartite-check.html)

# `coloring_result`

```elixir
@type coloring_result() ::
  {non_neg_integer(), %{required(Yog.node_id()) =&gt; 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`

```elixir
@type exact_result() ::
  {:ok, pos_integer(), %{required(Yog.node_id()) =&gt; pos_integer()}}
  | {:timeout, coloring_result()}
```

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

# `coloring_dsatur`

```elixir
@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`

```elixir
@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`

```elixir
@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.

---

*Consult [api-reference.md](api-reference.md) for complete listing*