Colors

Colors, or more specifically vertex colors, are a powerful tool when modelling objects as graphs. On this page, we explain the meaning of colors, and how to make use of them.

To avoid any confusion, the colors discussed here have nothing to do with colorings discussed in the well-known “graph coloring problems”.

What do vertex colors mean? #

Vertex colors restrict the potential set of symmetries. Vertices that are colored differently, can never be mapped to each other using a symmetry. Or phrased differently, a symmetry of a graph may only map equally colored vertices onto each other.

Formally, given a graph \(G = (V, E)\), a vertex coloring is a map \(\pi : V \to \mathbb{N}\). We may construct the vertex-colored graph \(G’ := (V, E, \pi)\). Recall that for the uncolored graph \(G\), a symmetry is a bijection \(\varphi : V \to V\) that satisfies \(\varphi((V, E)) = (V, E)\).

For the vertex-colored version \(G’\), we additionally require that for all \(v_1, v_2 \in V\), if \(\varphi(v_1) = v_2\), then \(\pi(v_1) = v_2\) holds.

Coloring Graphs #

We construct the vertex-colored graph above in dejavu. We identify the color blue with 0, orange with 1, and red with 2. We highlight the lines where the red and orange vertices are added to the graph.

dejavu::static_graph g;
g.initialize_graph(7, 6);          // 7 vertices, 6 edges

// the colors
constexpr int blue   = 0;
constexpr int orange = 1;
constexpr int red    = 2;

// add vertices
const int v0 = g.add_vertex(blue,   2); // center of the graph
const int v1 = g.add_vertex(orange, 3); // the orange vertex
const int v2 = g.add_vertex(red,    3); // the red vertex
const int v3 = g.add_vertex(blue,   1); // leaf 
const int v4 = g.add_vertex(blue,   1); // leaf
const int v5 = g.add_vertex(blue,   1); // leaf
const int v6 = g.add_vertex(blue,   1); // leaf

// add edges
g.add_edge(v0, v1);
g.add_edge(v0, v2);
g.add_edge(v1, v3);
g.add_edge(v1, v4);
g.add_edge(v2, v5);
g.add_edge(v2, v6);

The function add_vertex(int color, int degree) adds a vertex to the graph, where the first parameter is the “color” of the vertex, and the second parameter the degree in the graph (the number of edges connected to the vertex).