Menu
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, \ldots, 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.