A coloring of a graph G is an assignment of colors to its vertices such that adjacent vertices have different colors. Two colorings of a graph are equivalent if they induce the same partition of the vertex set into stable sets (i.e., sets of pairwise non-adjacent vertices). The n-th Bell number is the number of partitions of a set of n elements into non-empty subsets and is thus the same as the number of non-equivalent colorings of the empty graph or order n (i.e., the graph with n vertices and without any edge).
We are interested in the average number A(G) of colors in the non-equivalent colorings of a graph G. We give properties of this new graph invariant and show how it can help derive inequalities for the Bell numbers. We then prove some bounds on A(G). In particular, we give a general upper bound on A(G) that is valid for all graphs G and a more precise one for graphs G of order n and maximum degree in {1, 2, n − 2}. We then conjecture several lower bounds on 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. We finish with many open questions.