I would like to find the chromatic polynomial χ for the n by m rook's graph Gn,m for as many values of n and m possible. The rooks graph is also (a) the line graph of the complete bipartite graph Kn,m and (b) the Cartesian product of Kn and Km.
This is going to be very difficult in general since, for example, χ(Gn,n;x) evaluated at x=n is the number of Latin squares of order n (which is known only for n≤11). In general, χ(Gn,m;x) counts a generalisation of Latin squares. Moreover, Gn,m typically has lots of edges, making the standard deletion/contraction computation infeasible.
However, if we find enough values of χ(Gn,m;x) for small x we can simply fit a polynomial to these points to find χ(Gn,m;x) itself. For rook's graphs, it may be possible to find values of χ(Gn,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)?
No comments:
Post a Comment