# Coloring

*LightGraphs.jl* defines a structure and basic interface for coloring algorithms. Since coloring is a hard problem in the general case, users can extend the behavior and define their own function taking a graph as input and returning the `Coloring`

structure.

`LightGraphs.Coloring`

`LightGraphs.degree_greedy_color`

`LightGraphs.greedy_color`

`LightGraphs.perm_greedy_color`

`LightGraphs.random_greedy_color`

`LightGraphs.Coloring`

— Type`struct Coloring{T}`

Store the number of colors used and mapping from vertex to color

`LightGraphs.degree_greedy_color`

— Method`degree_greedy_color(g)`

Color graph `g`

iteratively in the descending order of the degree of the vertices.

`LightGraphs.greedy_color`

— Method`greedy_color(g; sort_degree=false, reps = 1)`

Color graph `g`

based on Greedy Coloring Heuristics

The heuristics can be described as choosing a permutation of the vertices and assigning the lowest color index available iteratively in that order.

If `sort_degree`

is true then the permutation is chosen in reverse sorted order of the degree of the vertices. `parallel`

and `reps`

are irrelevant in this case.

If `sort_degree`

is false then `reps`

colorings are obtained based on random permutations and the one using least colors is chosen.

`LightGraphs.perm_greedy_color`

— Method`perm_greedy_color(g, seq)`

Color graph `g`

according to an order specified by `seq`

using a greedy heuristic. `seq[i] = v`

implies that vertex v is the $i^{th}$ vertex to be colored.

`LightGraphs.random_greedy_color`

— Method`random_greedy_color(g, reps)`

Color the graph `g`

iteratively in a random order using a greedy heuristic and choose the best coloring out of `reps`

such random colorings.