Extremal Restraints for Graph Colourings

Abstract

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.