Group for Research in Decision Analysis

G-2015-04

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

, , , and

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