Restraints permitting the largest number of colourings

A restraint r on G is a function which assigns each vertex v of G a finite set of forbidden colours r(v). A proper colouring c of G is said to be permitted by the restraint r if c(v)∉r(v) for every vertex v of G. A restraint r on a graph G with n vertices is called a k-restraint if ∣r(v)∣=k and r(v)⊆{1,2,…,kn} for every vertex v of G. In this article we discuss the following problem: among all k-restraints r on G, which restraints permit the largest number of x-colourings for all large enough x? We determine such extremal restraints for all bipartite graphs.