Graph Coloring

Graph Coloring

• two_color(G): return a two-coloring of the graph (if bipartite).
• bipartition(G): return a partition of the vertex set into two independent sets (if bipartite). See the SimplePartitions module.
• greedy_color(G,vertex_list): greedily color the vertices in the order specified by vertex_list.
• random_greedy_color(G,reps): repeatedly color the vertices of the graph with random orderings of the vertices.

See SimpleGraphAlgorithms for more coloring functions.

Visualizing

The output of two_color, greedy_color, random_greedy_color, and—from SimpleGraphAlgorithms—the vertex_color functions is a dictionary mapping vertices to positive integers. We provide the colorize function that converts the integers to actual colors and applies them to vertices.

The bipartition function returns a partition of the vertex set of the graph into two independent sets (assuming the graph is bipartite). Use bipartite_colorize to color the vertices according to the bipartition.

For example:

julia> using SimpleGraphs, SimpleGraphAlgorithms, DrawSimpleGraphs

julia> G = Icosahedron()
Icosahedron (n=12, m=30)

julia> c = vertex_color(G,4);

julia> colorize(G,c)

julia> draw(G)

julia> G = Cube(3)
Cube(3) (n=8, m=12)

julia> bipartite_colorize(G)

julia> draw(G)