Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T16:07:47.547Z Has data issue: false hasContentIssue false

Galois groups of chromatic polynomials

Published online by Cambridge University Press:  01 September 2012

Kerri Morgan*
Affiliation:
Clayton School of Information Technology, Monash University, Building 63, Wellington Road, Clayton 3800, Australia (email: Kerri.Morgan@monash.edu)

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The chromatic polynomial P(G,λ) gives the number of ways a graph G can be properly coloured in at most λ colours. This polynomial has been extensively studied in both combinatorics and statistical physics, but there has been little work on its algebraic properties. This paper reports a systematic study of the Galois groups of chromatic polynomials. We give a summary of the Galois groups of all chromatic polynomials of strongly non-clique-separable graphs of order at most 10 and all chromatic polynomials of non-clique-separable θ-graphs of order at most 19. Most of these chromatic polynomials have symmetric Galois groups. We give five infinite families of graphs: one of these families has chromatic polynomials with a dihedral Galois group and two of these families have chromatic polynomials with cyclic Galois groups. This includes the first known infinite family of graphs that have chromatic polynomials with the cyclic Galois group of order 3.

Information

Type
Research Article
Copyright
Copyright © London Mathematical Society 2012