My paper with Kerri Morgan on algebraic properties of chromatic roots (described here) has just appeared in the Electronic Journal of Combinatorics: you can find it here.
I won’t say any more about it, except to pose a challenge which we were unable to solve. We found graphs for which the Galois groups of irreducible factors of the chromatic polynomial include all transitive groups of degree at most 4, and all of degree 5 with a single exception; for larger degree, the gaps become wider and wider … So here is the challenge:
Is there a graph whose chromatic polynomial has an irreducible factor with Galois group cyclic of order 5? [Preferably the chromatic polynomial should be a product of this factor and n−5 linear factors.]
Advertisements
Hi Peter,
Hamish Gilmore (who did his Masters with me) found a (5,k)-biclique with Galois groups C(5).
It has 181 edges, 23 vertices, and interesting factor g(x) = x^5-65x^4+1679x^3-21530x^2+136953x-345421.
In fact, he found exactly five quintic number fields F arising from (5,k)-bicliques with Galois group C(5), and whose discriminant D_F has magnitude <= 2 \times 10^7.
See Chapter 7 of Hamish's thesis, available at: http://researchcommons.waikato.ac.nz/handle/10289/9367
Best, Daniel.
Excellent! On to degree 6? There are lots of gaps there! But it does suggest that bicliques are a good place to look.