Algebraic properties of chromatic polynomials, 2

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

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in open problems, Uncategorized and tagged , , . Bookmark the permalink.

2 Responses to Algebraic properties of chromatic polynomials, 2

  1. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s