Analysis of Complex Networks

1.5 Alternative Bases for Structural Complexity

Colorings of a graph can be used to obtain a decomposition of the vertices. Sets of vertices of the same color (or independent sets) constitute equivalence classes. Unlike the orbits of the automorphism group, a partition of the vertices obtained in this way is not unique. However, an information measure may be defined by taking the minimum value over some set of decompositions linked to colorings [16]. This section explores such a measure, compares it with the symmetry-based measure, and shows its relationship to the graph entropy as defined in [11].

A coloring of a graph is an assignment of colors to the vertices so that no two adjacent vertices have the same color.

An n-coloring of a graph G = (V, E) is a coloring with n colors or, more precisely, a mapping f of V onto the set {1, 2,..., n} such that whenever [u, v] ∈ E, f(u) ≠ f(v).

The chromatic number κ(G) of a graph G is the smallest value of n for which there is an n-coloring. A graph may have more than one n-coloring.

An n-coloring is complete if, for every i, j with i ≠ j, there exist adjacent vertices u and v such that f(u) = i and f(v) = j.

A decomposition of the set of vertices V is called a chromatic decomposition of G if u, v ∈ V_i imply that [u, v] ∉ E. Note that V_i in a chromatic decomposition is a set of independent vertices. If f is an n-coloring, the collection of ...