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 BibTeX reference
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.
Published January 2015 , 14 pages
Research Axis
Publication
Jan 2018
, , , and
Discrete Applied Mathematics, 234, 3–11, 2018
BibTeX reference