It's in Knuth, so it must be true! "Let's return to the graph of contiguous states for one more example. That graph is planar; suppose we want to color it with four colors. Since the colors can be given 2-bit codes {00, 01, 10, 11}, it's easy to express the valid colorings as a Boolean function of 98 variables that is true if and only if the color codes ab are different for each pair of adjacent states: COLOR(a_ME, b_ME, ..., a_CA,b_CA) = ... Each of the four INDs has a BDD of 854 nodes, which can be computed via (72) with a cost of about 70 kilomems. The COLOR function turns out to have only 25579 BDD nodes. Algorithm C now quickly establishes that the total number of ways to 4-color this graph is exactly 25,623,183,458,304 -- or, if we divide by 4! to remove symmetries, about 1.1 trillion." - D. E. Knuth. The Art of Computer Programming. vol 4A. Combinatorial Algorithms. 7.1.4 Binary Decision Diagrams. Page 233. 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.
-- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com