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.
Published November 2013 , 18 pages
Research Axis
Publication
Apr 2016
and
Discrete Applied Mathematics, 203, 62–71, 2016
BibTeX reference
Document
G1382.pdf (500 KB)