Group for Research in Decision Analysis

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

## Romain Absil, Eglantine Camby, Alain Hertz, and Hadrien Mélot

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 $$\mathcal{B}(G)$$ is the number of non-equivalent vertex colorings of $$G$$. We determine a sharp lower bound on $$\mathcal{B}(G)$$ for graphs $$G$$ of order $$n$$ and maximum degree $$n-3$$, and we characterize the graphs for which the bound is attained.

, 14 pages