Back

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.

, 14 pages

Research Axis

Publication

, , , and
Discrete Applied Mathematics, 234, 3–11, 2018 BibTeX reference