Gap-Neighbour-Distinguishing Colourings

Abstract

In this work, we investigate the gap-adjacent-chromatic number, a graph colouring parameter introduced by M. A. Tahraoui, E. Duchéne, and H. Kheddouci in $[5]$. From an edge labelling $f:E\to \{1,\dots ,k\}$ of a graph $G=(V,E)$, the vertices of $G$ get an induced colouring. Vertices of degree greater than one are coloured with the difference between their maximum and their minimum incident edge label, i.e., with their so-called gap, and vertices of degree one get their incident edge label as colour. The gap-adjacent-chromatic number of $G$ is the minimum $k$ for which a labelling $f$ of $G$ exists that induces a proper vertex colouring.

The main purpose of this work is to state easy colouring approaches for bipartite graphs and to estimate the gap-adjacent-chromatic number for arbitrary graphs in terms of the chromatic number.