Graphs.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.

struct Coloring{T}

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

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.

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.

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.