In case the chromatic polynomial does not come through here it is again in a different format. x*(x-1)^3*(x-2)^12*(x^31-74*x^30+2662*x^29-62009*x^28+1051192*x^27-13817954*x^26+146540197*x^25-1287959730*x^24+ 9563897097*x^23-60861199906*x^22+335505665807*x^21-1615450771201*x^20+6836940711775*x^19-25554817600059*x^18+ 84651979013714*x^17-249103966596626*x^16+652062513996036*x^15-1518903799875716*x^14+ 3146686741088193*x^13-5788570890576155*x^12+9430091492582543*x^11-13550867810367132*x^10+ 17082113473194601*x^9-18750992054746828*x^8+17746420485663203*x^7-14289063407025521*x^6+ 9610593113770304*x^5-5261190717302787*x^4+2255365841830048*x^3-711273204791358*x^2+146988563481064*x-14958585349094)*(x-3)^2 Maple found it in 56.7 seconds. On Thu, Feb 21, 2013 at 3:33 PM, W. Edwin Clark <wclark@mail.usf.edu> wrote:
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