Certificates of factorisation for chromatic polynomials
Summary: The chromatic polynomial gives the number of proper \(\lambda\)-colourings of a graph \(G\). This paper considers factorisation of the chromatic polynomial as a first step in an algebraic study of the roots of this polynomial. The chromatic polynomial of a graph is said to have a chromatic factorisation if \(P(G,\lambda)= P(H_1,\lambda)P(H_2,\lambda)/P(K_r,\lambda)\) for some graphs \(H_1\) and \(H_2\) and clique \(K_r\). It is known that the chromatic polynomial of any clique-separable graph, that is, a graph containing a separating \(r\)-clique, has a chromatic factorisation. We show that there exist other chromatic polynomials that have chromatic factorisations but are not the chromatic polynomial of any clique-separable graph and identify all such chromatic polynomials of degree at most 10. We introduce the notion of a certificate of factorisation, that is, a sequence of algebraic transformations based on identities for the chromatic polynomial that explains the factorisations for a graph. We find an upper bound of \(n^22^{n^2/2}\) for the lengths of these certificates, and find much smaller certificates for all chromatic factorisations of graphs of order \(\leq9\).
- An algorithm which outputs a graph with a specified chromatic factor
- Factorisation of greedoid polynomials of rooted digraphs
- Certificates of factorisation for a class of triangle-free graphs
- Certificates for properties of stability polynomials of graphs
- Non-bipartite chromatic factors
- Short certificates for chromatic equivalence
- Pairs of chromatically equivalent graphs
- Graph polynomials: some questions on the edge
- An infinite family of 2-connected graphs that have reliability factorisations
This page was built for publication: Certificates of factorisation for chromatic polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380229)
