An algorithm which outputs a graph with a specified chromatic factor

For an undirected graph G, the chromatic polynomial is a key specialisation of its Tutte polynomial. The “(α + n)-conjecture” states that given any algebraic integer α, for large enough [Formula presented] the shifted value α + n is the root of some chromatic polynomial. We develop an algorithm whose input is a monic polynomial [Formula presented] of degree d≤4, and the output is a (d,N)-biclique whose chromatic polynomial is a product of linear factors and the factor Pd(X−n) where [Formula presented] is taken to be sufficiently large, provided that such a (d,N)-biclique exists. In degree d = 3 our method tends to produce smaller (3,N)-bicliques than Adam Bohn's cubic parameterisation (Bohn, 2014), while in degree d = 4 it provides an efficient way to check the (α + n)-conjecture for a given quartic polynomial. The construction relies on previous work of Farrell (1980) which interprets chromatic coefficients via induced subgraphs, together with a simple search algorithm that is based on the number of ways to partition an integer. We also derive new expressions for the interesting factors of the chromatic polynomials for (3,N)-bicliques and (4,N)-bicliques, in terms of these induced subgraphs.