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 , its chromatic polynomial counts proper colourings with available colours at nonnegative integers . It is monic in . If is the chromatic number, then
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
- Bohn2012Chromatic · §1, p. 543Source
Example
Example
The quadratic has discriminant . Thus the splitting field is and the Galois group is . For , two quadratic factors occur, but both split in this same field. Their groups do not form a direct product.
References 1
- Morgan2012Chromatic · §2, pp. 283–284Source
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 by an irreducible polynomial also occurs on an irreducible chromatic factor. This implication does not solve the inverse Galois problem.
References 2
- Bohn2012Chromatic · Abstract and §§2–4Source
- CameronMorgan2017 · §6Source
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
- Morgan2012Chromatic · §§5–6Source
- GoodallJouveSereni2025Tutte · §1, pp. 2–3Source
Questions
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 conjecture. It is known in degrees at most three.
References 2
- CameronMorgan2017 · Conjecture 1.1Source
- Bohn2012Chromatic · Abstract and §§2–4Source
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 conjecture. It is distinct from closure under nonnegative integer translation, which is known.
References 1
- CameronMorgan2017 · Proposition 1.3 and Conjecture 1.2Source
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 , and the limit .
References 1
- CameronMorgan2017 · §6.1, Conjecture 6.1Source
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
- CameronMorgan2017 · §6.1, paragraph after Conjecture 6.1Source
Related topics
Tutte polynomials
The chromatic polynomial is obtained from the Tutte polynomial by a fixed specialization.
CompareSpecialization and Hilbert irreducibility
Generic Galois groups can drop at a specified specialization.
UsesDiscriminants, parity, and ramification
Discriminants distinguish cyclic cubic groups from symmetric ones.
Linked from 1 articles
References
- Chromatic roots as algebraic integers
Bohn, Adam. DMTCS Proceedings, FPSAC 2012, AR, 543–554, 2012.
Read the source - Galois groups of chromatic polynomials
Morgan, Kerri. LMS Journal of Computation and Mathematics, 15, 281–307, 2012.
Read the source - Algebraic properties of chromatic roots
Cameron, Peter J. and Morgan, Kerri. The Electronic Journal of Combinatorics, 24(1), P1.21, 2017.
Read the source - 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
Comments
Any comments are welcome. Comments appear after the site owner approves them. Privacy policy.