In this paper we introduce the notion of $Sigma$-colouring of a graph $G$: For given subsets $Sigma(v)$ of neighbours of $v$, for every $vin V(G)$, this is a proper colouring of the vertices of $G$ such that, in addition, vertices that appear together in some $Sigma(v)$ receive different colours. This concept generalises the notion of colouring the square of graphs and of cyclic colouring of graphs embedded in a surface. We prove a general result for graphs embeddable in a fixed surface, which implies asymptot
Download