You can use the method of deletion and contraction (or its converse): Let F(G) be the chromatic polynomial of G. 1) if G = G1 union G2 as disjoint graphs then F(G) = F(G1) F(G2) 2) Let e be an edge of G, and let G1 be the graph that you get by deleting e, and G2 the graph you get by contracting e (i.e. identify the end points. Then F(G) = F(G1) - F(G2). Do that recursively, and cache isomorphic subgraphs. The converse way (if the graph is close to a complete graph) is to add edges. Victor On Thu, Feb 21, 2013 at 2:01 PM, Dan Asimov <dasimov@earthlink.net> wrote:
How does one calculate the chromatic polynomial without knowing the number of k-colorings for k <= #(V) ?
--Dan
On 2013-02-20, at 11:27 PM, rcs@xmission.com wrote:
The chromatic polynomial is probably doable.
Rich
------ Quoting David Wilson <davidwwilson@comcast.net>:
So just how many 4-colorings of the U.S. map are there?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun