Using the data from http://www-cs-staff.stanford.edu/~uno/contiguous-usa.dat and Maple's ChromaticPolynomial procedure I get the polynomial which is 0 for x = 1,2,3 and for x = 4 gives 25623183458304, the number of 4-colorings. On Thu, Feb 21, 2013 at 2:50 PM, Victor Miller <victorsmiller@gmail.com>wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun