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 referenceTwo 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