Homogeneous colourings of graphs

Abstract

A proper vertex $k$-colouring of a graph $G$ is called $l$-homogeneous if the number of colours in the neigbourhood of each vertex of $G$ equals $l$. We explore basic properties (the existence and the number of used colours) of homogeneous colourings of graphs in general as well as of some specific graph families, in particular planar graphs.

Keywords

• proper colouring
• homogeneous colouring
• planar graph
• triangulation