From: Matthew Hubbard <leofosse@crl.com>
Subject: Re: Chromatic polynomials and graph coloring
Date: Sat, 22 Jan 2000 23:26:18 -0800
Newsgroups: sci.math
Summary: Stanley's theorem: painting with -1 colors

Henrik Bäärnhielm wrote:
> 
> Hi
> 
> Could anyone give me some hints of every-day problems that can be
> modeled and solved using graph coloring and especially chromatic
> polynomials, that is, something involving the number of possible
> colorings of a graph?
> I am studying graph theory right now at my university, and all my
> textbooks mention that many problems is really a matter of graph
> coloring in some way, but they don't really give any examples, and I
> can't figure out something good myself... :(

	The oddest use of the chromatic polynomial of a graph p(G,x) is
Stanley's Theorem, which states that the number of acyclic orientations
of G (i.e., the number of ways do put directions - or orientations - on
all the edges that produce no directed cycles) is (-1)^n(p(G,-1)).  In
other words, it's the aboslute value of the number of ways to paint G
properly using -1 colors.

Strange, but true,
MattH