## 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 ...