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.