  We study the average number $\mathcal{A}(G)$ of colors in the non-equivalent
colorings of a graph $G$. We show some general properties of this graph
invariant and determine its value for some classes of graphs. We then
conjecture several lower bounds on $\mathcal{A}(G)$ and prove that these
conjectures are true for specific classes of graphs such as triangulated graphs
and graphs with maximum degree at most 2.
