chromatic polynomial connection

55 views
Skip to first unread message

ohan math

unread,
Jul 11, 2026, 3:40:09 AM (3 days ago) Jul 11
to SeqFan

dear all,

who may be an editor of Oeis who is an expert in calculating the chromatic polynomials?

the sequence A211709 has currently 39 terms calculated.

more terms seem to be computed easily.

the task is the compute the vertex-chromatic polynomial of (n x m) rook's graph.

it is a simple observation that the terms of A211709 are just the summation of coefficients of this polynomial (written in factorial basis representation)

for example, (3, 3)th term of the sequence is 588.
which is also the summation of the coefficients of the vertex-chromatic polynomial of 3x3 rook's graph.
588 = 2 + 42 + 186 + 234 + 105 + 18 + 1

this polynomial for 5x5 rook's graph seems to be calculated in seconds. this will correspond to the (5,5)th term of the sequence which is currently missing.

i do not have experience on obtaining chromatic polynomials. 
how far can we compute these polynomials? 7x7 is possible? or 8x8?

may i contact with an expert on calculating chromatic polynomials in order to update this sequence in Oeis.



A Howroyd

unread,
Jul 11, 2026, 9:01:01 PM (2 days ago) Jul 11
to SeqFan
Because this is related to Latin squares:
  - this is a difficult problem (Number of Latin squares are known up to 11 X 11, but allowing more than n colors makes the problem harder)
 - if you have more terms, then you should add them: 4 X 6 and 5 X 5 will complete the next diagonal.
 - you might also add A295184(5)
 - generic software for computing chromatic polynomials is unlikely to be of much use for higher n - since it won't exploit permutation of row/columns symmetry. The endeavors to compute the number of Latin squares exploit this symmetry. (Brendan Mckay, the author of nauty is one of the main experts in this, but presumably the program he has is not "yet" tailored to do this or perhaps he has just not run on this sequence).  These things also take countless hours of cpu. (the last time Brendan recomputed a missing value for me he used up like 2 cpu years in one night!!!). 
Reply all
Reply to author
Forward
0 new messages