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 ij, there exist adjacent vertices u and v such that f(u) = i and f(v) = j.

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

Get Analysis of Complex Networks now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.