Chromatic Factors

The chromatic polynomial P(G, λ) gives the number of proper colourings of a graph G in at most λ colours. If P(G, λ) = P(H₁, λ) P(H₂, λ) /P(K_r, λ), then G is said to have a chromatic factorisation of order r with chromatic factors H₁ and H₂. It is clear that, if 0 ≤ r ≤ 2, any H₁≇ K_r with chromatic number X(H₁) ≥ r is the chromatic factor of some chromatic factorisation of order r. We show that every H₁ ≇ K₃ with X(H₁) ≥ 3, even when H₁ contains no triangles, is the chromatic factor of some chromatic factorisation of order 3 and give a certificate of factorisation for this chromatic factorisation. This certificate shows in a sequence of six steps using some basic properties of chromatic polynomials that a graph G has a chromatic factorisation with one of the chromatic factors being H₁. This certificate is one of the shortest known certificates of factorisation, excluding the trivial certificate for chromatic factorisations of clique-separable graphs.