Extremal Restraints for Graph Colourings

Abstract

A {\em 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 {\em 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 {\em forbidden} at $v$). Given a large number of colors, for restraints $r$ with exactly one colour forbidden at each vertex the smallest number of colorings 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.

7 pages, 1 figure

Cited by in corpus (1)

• Maximum number of colourings. II. 5-chromatic graphs