Tutorial

Let's explore how to use the QuasiStableColors library with an example.

Installation

First, install the library. One option is to run the following code:

using Pkg
Pkg.add("QuasiStableColors")

After installing activate the libary:

using QuasiStableColors

Coloring Graphs

Let's create a simple example graph.

using Graphs
n = 8
g = Graphs.SimpleGraphs.dorogovtsev_mendes(n, seed=0)

using GraphMakie, CairoMakie
graphplot(g)

Example network graph from above code

Now, let's generate a quasi-stable coloring C where we allow at most one edge error (i.e. $q=1$).

C = QuasiStableColors.q_color(g, q=1.0)
4-element Vector{Vector{Int64}}:
 [5, 6, 7, 8, 1]
 [4]
 [2]
 [3]

We get a four-partition coloring. Let's assign a unique graphical color to each:

using Colors
palette = distinguishable_colors(length(C))
color_map = Array{Colorant}(undef, nv(g))
for (i, x) in enumerate(C)
    color_map[x] .= palette[i]
end

and draw the graph again:

graphplot(g, node_color=color_map)

Same graph, now colored according to above partition

Approximation

This section on how to use the coloring for graph algorithms is upcoming–for now see the maximum-flow section of the API reference as an example.