{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T06:33:25Z","timestamp":1780382005629,"version":"3.54.1"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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^{2}2^{n^{2}\/2}$ for the lengths of these certificates, and find much smaller certificates for all chromatic factorisations of graphs of order $\\leq 9$.<\/jats:p>","DOI":"10.37236\/163","type":"journal-article","created":{"date-parts":[[2020,1,11]],"date-time":"2020-01-11T04:29:01Z","timestamp":1578716941000},"source":"Crossref","is-referenced-by-count":6,"title":["Certificates of Factorisation for Chromatic Polynomials"],"prefix":"10.37236","volume":"16","author":[{"given":"Kerri","family":"Morgan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Graham","family":"Farr","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"23455","published-online":{"date-parts":[[2009,6,19]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v16i1r74\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v16i1r74\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,18]],"date-time":"2020-01-18T02:52:37Z","timestamp":1579315957000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v16i1r74"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6,19]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2009,1,7]]}},"URL":"https:\/\/doi.org\/10.37236\/163","relation":{},"ISSN":["1077-8926"],"issn-type":[{"value":"1077-8926","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6,19]]},"article-number":"R74"}}