Overview

  • Which linear factors are forced by the chromatic number?
  • Does every algebraic integer become a chromatic root after an integer shift?
  • What is conjectured about the nonlinear factors of a random graph?

Definition

For a finite simple graph GG, its chromatic polynomial PG(q)P_G(q) counts proper colourings with qq available colours at nonnegative integers qq. It is monic in Z[q]\mathbb Z[q]. If χ(G)\chi(G) is the chromatic number, then

∏j=0χ(G)−1(q−j)∣PG(q).\prod_{j=0}^{\chi(G)-1}(q-j)\mid P_G(q).

Irreducibility questions therefore concern the remaining factors. When removing all linear factors, include their full multiplicities. Since the polynomial is monic, every rational root is an integer.

References 1

Example

Example

PC4(q)=q(q−1)(q2−3q+3).P_{C_4}(q)=q(q-1)(q^2-3q+3).

The quadratic has discriminant −3-3. Thus the splitting field is Q(−3)\mathbb Q(\sqrt{-3}) and the Galois group is C2C_2. For C7C_7, two quadratic factors occur, but both split in this same field. Their groups do not form a direct product.

References 1

Algebraic integers

The shift and multiplication conjectures are stated below. Bohn proves the shift conjecture for algebraic integers of degree at most three and constructs a dense set of chromatic roots closed under multiplication by positive integers.

The shift question has a Galois interpretation: translating a monic irreducible polynomial changes neither its splitting field nor its permutation group. If every algebraic integer has the required shift, every group already realized over Q\mathbb Q by an irreducible polynomial also occurs on an irreducible chromatic factor. This implication does not solve the inverse Galois problem.

References 2

Specialization

Morgan constructs infinite graph families with cyclic and dihedral groups. Thus the group of a chromatic polynomial need not be symmetric. The random-graph conjecture below asks about the proportion of graphs, so these special families are compatible with it.

Similarly, the generic group of a Tutte polynomial does not determine the group of every chromatic specialization.

References 2

Questions

OpenPolynomial families

Does every algebraic integer become a chromatic root after an integer shift?

Scope. For every algebraic integer α, seek an integer n≥0 and a finite graph G with P_G(α+n)=0.

This is the α+n\alpha+n conjecture. It is known in degrees at most three.

References 2
Discuss this question →
OpenPolynomial families

Are positive integer multiples of chromatic roots again chromatic roots?

Scope. If α is a root of some chromatic polynomial, and m≥1, ask whether mα is also a chromatic root.

This is the nαn\alpha conjecture. It is distinct from closure under nonnegative integer translation, which is known.

References 1
Discuss this question →
OpenPolynomial families

Does a random graph have one nonlinear chromatic factor with symmetric group?

Scope. Cameron–Morgan (2017), Conjecture 6.1; the source uses the informal word “typically”.

After the linear factors are removed, the conjectured remaining factor is irreducible with the full symmetric group. A precise probabilistic version must specify the graph model, for example G(N,1/2)G(N,1/2), and the limit N→∞N\to\infty.

References 1
Discuss this question →
OpenPolynomial families

Which graphs have chromatic polynomials that split completely over Q?

Scope. Finite simple graphs; all factors of P_G(q) are linear over Q.

Chordal graphs have this property, but they are not the only ones. The cited source asks for a characterization.

References 1
Discuss this question →

Related topics

References

  1. Chromatic roots as algebraic integers

    Bohn, Adam. DMTCS Proceedings, FPSAC 2012, AR, 543–554, 2012.

    Read the source
  2. Galois groups of chromatic polynomials

    Morgan, Kerri. LMS Journal of Computation and Mathematics, 15, 281–307, 2012.

    Read the source
  3. Algebraic properties of chromatic roots

    Cameron, Peter J. and Morgan, Kerri. The Electronic Journal of Combinatorics, 24(1), P1.21, 2017.

    Read the source
  4. On the irreducibility and monodromy of Tutte polynomials

    Goodall, Andrew and Jouve, Florent and Sereni, Jean-Sébastien. arXiv:2510.05658v1, 2025.

    Read the source