Extremal Restraints for Graph Colourings

A restraint on a (finite undirected) graph \( G = (V, E) \) is a function \( r \) on \( V \) such that \( r(v) \) is a finite subset of \( \mathbb{N} \); a proper vertex colouring \( c \) of \( G \) is permitted by \( r \) if \( c(v) \notin r(v) \) for all vertices \( v \) of \( G \) (we think of \( r(v) \) as the set of colours forbidden at \( v \)). Given a large number of colors, for restraints \( r \) with exactly one colour forbidden at each vertex the smallest number of colourings is permitted when \( r \) is a constant function, but the problem of what restraints permit the largest number of colourings is more difficult. We determine such extremal restraints for complete graphs and trees.