most recent 30 from http://mathoverflow.net 2013-06-19T08:13:19Z http://mathoverflow.net/feeds/question/19486 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/19486/finding-a-chromatic-polynomial-by-polynomial-fitting Douglas S. Stones 2010-03-27T04:54:21Z 2010-03-27T04:54:21Z

<p>I would like to find the <a href="http://en.wikipedia.org/wiki/Chromatic_polynomial" rel="nofollow">chromatic polynomial</a> &chi; for the n by m <a href="http://en.wikipedia.org/wiki/Rook%27s_graph" rel="nofollow">rook's graph</a> G_n,m for as many values of n and m possible. The rooks graph is also (a) the line graph of the complete bipartite graph K_n,m and (b) the Cartesian product of K_n and K_m.</p> <p>This is going to be very difficult in general since, for example, &chi;(G_n,n;x) evaluated at x=n is the number of <a href="http://en.wikipedia.org/wiki/Latin_square" rel="nofollow">Latin squares</a> of order n (which is known only for n&le;11). In general, &chi;(G_n,m;x) counts a generalisation of Latin squares. Moreover, G_n,m typically has lots of edges, making the standard deletion/contraction computation infeasible.</p> <p>However, if we find enough values of &chi;(G_n,m;x) for small x we can simply fit a polynomial to these points to find &chi;(G_n,m;x) itself. For rook's graphs, it may be possible to find values of &chi;(G_n,m;x) efficiently by generalising techniques used in counting Latin squares.</p> <p>I would like to know if it is ever feasible to find a chromatic polynomial via polynomial fitting in some cases, that cannot be found using deletion/contraction?</p> <blockquote> <p><strong>Question</strong>: Are there examples in the literature in which a chromatic polynomial was found by polynomial fitting small data points (which could not be found faster using deletion/contraction)?</p> </blockquote>