A note on the neighbour-distinguishing index of digraphs - Sopena, Éric (Ars mathematica contemporanea, 2023)
V članku vpeljemo in preučujemo novo različico barvanja lokov v digrafih, ki razlikuje sosede. Barvanje lokov ?$γ$? digrafa ?$D$? je pravilno, če nobenima dvema lokoma z istim koncem ali z istim začetkom ni dodeljena ista barva. Za vsako vozlišče ?$u$? digrafa ?$D$? označimo z ?$S_{γ}^- (u)$? in ?$S_{γ}^+ (u)$? množici barv, ki nastopata na vhodnih lokih in na izhodnih lokih vozlišča ?$u$?. Barvanje lokov ?$γ$? digrafa ?$D$? razlikuje sosede, če sta za vsaka dva sosedna vozlišča ?$u$? in ?$v$? digrafa ?$D$?, urejena para ?$(S_{γ}^- (u), S_{γ}^ + (u))$? in ?$(S_{γ}^- (v), S_{γ}^+ (v))$? različna. Indeks razlikovanja sosedov digrafa ?$D$? je potem najmanjše število barv, ki so potrebne za barvanje lokov, ki razlikuje sosede v digrafu ?$D$?. Dokažemo zgornje meje za indeks razlikovanja sosedov različnih razredov digrafov.
Keywords: arc-colouring; barvanje lokov; barvanje lokov, ki razlikuje sosede; digraf; digraph; neighbour-distinguishing arc-colouring