A note on the neighbour-distinguishing index of digraphs

Éric Sopena, Mariusz Woźniak


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.


Digraph, arc-colouring, neighbour-distinguishing arc-colouring

Full Text:


DOI: https://doi.org/10.26493/1855-3974.2144.9e3

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications