  We establish a connection between root multiplicities for Borcherds-Kac-Moody
algebras and graph coloring. We show that the generalized chromatic polynomial
of the graph associated to a given Borcherds algebra can be used to give a
closed formula for certain root multiplicities. Using this connection we give a
second interpretation, namely that the root multiplicity of a given root
coincides with the number of acyclic orientations with a unique sink of a
certain graph (depending on the root). Finally, using the combinatorics of
Lyndon words we construct a basis for the root spaces corresponding to these
roots and determine the Hilbert series in the case when all simple roots are
imaginary. As an application we give a Lie theoretic proof of Stanley's
reciprocity theorem of chromatic polynomials.
