Counting the number of non-equivalent vertex colorings of a graph

We give some extremal properties on the number B(G)B(G) of non-equivalent ways of coloring a given graph GG, also known as the (graphical) Bell number of GG. In particular, we study bounds on B(G)B(G) for graphs with a maximum degree constraint. First, an upper bound on B(G)B(G) is given for graphs with fixed order nn and maximum degree ΔΔ. Then, we give lower bounds on B(G)B(G) for fixed order nn and maximum degree 1, 2, n−2n−2 and n−1n−1. In each case, the bound is tight and we describe all graphs that reach the bound with equality.