I would like to find the chromatic polynomial χ for the n by m rook's graph 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}.

This is going to be very difficult in general since, for example, χ(G_{n,n};x) evaluated at x=n is the number of Latin squares of order n (which is known only for n≤11). In general, χ(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.

However, if we find enough values of χ(G_{n,m};x) for small x we can simply fit a polynomial to these points to find χ(G_{n,m};x) itself. For rook's graphs, it may be possible to find values of χ(G_{n,m};x) efficiently by generalising techniques used in counting Latin squares.

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?

Question: 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)?