Back

G-2013-82

Counting the Number of Non-Equivalent Vertex Colorings of a Graph

and

BibTeX reference

We study the number \({\cal{P}}(G)\) of non-equivalent ways of coloring a given graph \(G\). We show some similarities and differences between this graph invariant and the well known chromatic polynomial. Relations with Stirling numbers of the second kind and with Bell numbers are also given. We then determine the value of this invariant for some classes of graphs. We finally study upper and lower bounds on \({\cal{P}}(G)\) for graphs with fixed maximum degree.

, 18 pages

Research Axis

Publication

and
Discrete Applied Mathematics, 203, 62–71, 2016 BibTeX reference

Document

G1382.pdf (500 KB)