Non-bipartite 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 1 , λ ) P ( H 2 , λ ) / P ( K r , λ ) , then G is said to have a chromatic factorisation of order r with chromatic factors H 1 and H 2 . It is clear that, if 0 ≤ r ≤ 2 , any H 1 ⁄ ≅ K r with chromatic number χ ( H 1 ) ≥ r is the chromatic factor of some chromatic factorisation of order r . We show that every H 1 ⁄ ≅ K 3 with χ ( H 1 ) ≥ 3 , even when H 1 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 seven steps using some basic properties of chromatic polynomials that a graph G has a chromatic factorisation with one of the chromatic factors being H 1 . This certificate is one of the shortest known certificates of factorisation, excluding the trivial certificate for chromatic factorisations of clique-separable graphs.