A sharp lower bound on the number of non-equivalent colorings of graphs of order n and maximum degree n−3

Two vertex colorings of a graph G are equivalent if they induce the same partition of the vertex set into color classes. The graphical Bell number B(G) is the number of non-equivalent vertex colorings of G. We determine a sharp lower bound on B(G) for graphs G of order n and maximum degree n−3, and we characterize the graphs for which the bound is attained.