A note on the neighbour-distinguishing index of digraphs - Sopena, Éric (Ars mathematica contemporanea, 2023)
In this note, we introduce and study a new version of neighbour-distinguishing arc-colourings of digraphs. An arc-colouring ?$γ$? of a digraph ?$D$? is proper if no two arcs with the same head or with the same tail are assigned the same colour. For each vertex ?$u$? of ?$D$?, we denote by ?$S_{γ}^- (u)$? and ?$S_{γ}^+ (u)$? the sets of colours that appear on the incoming arcs and on the outgoing arcs of ?$u$?, respectively. An arc colouring ?$γ$? of ?$D$? is neighbour-distinguishing if, for every two adjacent vertices ?$u$? and ?$v$? of ?$D$?, the ordered pairs ?$(S_{γ}^- (u), S_{γ}^+(u))$? and ?$(S_{γ}^- (v), S_{γ}^+ (v))$? are distinct. The neighbour-distinguishing index of ?$D$? is then the smallest number of colours needed for a neighbour-distinguishing arc-colouring of ?$D$?. We prove upper bounds on the neighbour-distinguishing index of various classes of digraphs.
Keywords: arc-colouring; barvanje lokov; barvanje lokov, ki razlikuje sosede; digraf; digraph; neighbour-distinguishing arc-colouring