NSD Edge-Colourings with Strong Assignment Constraints
Résumé
In this work, we introduce and study a combination of two types of graph edge-colourings, namely strong edge-colourings (in which every two edges at distance at most~$2$ must be assigned distinct colours) and neighbour-sum-distinguishing edge-colourings (in which adjacent edges must be assigned distinct colours, and every two adjacent vertices must be incident to distinct sums of colours). In particular, we investigate how the smallest number of colours in such combined edge-colourings behaves. For several classes of graphs, we prove that such edge-colourings are very close from strong edge-colourings, in the sense that no additional colours are required. For others classes of graphs, we prove that introducing more colours is sometimes necessary. We conjecture that, in general, designing this new type of edge-colourings should always be possible provided we are allowed to introduce and assign a constant number of additional colours. We prove this conjecture for a few classes of graphs, including trees and graphs of bounded maximum degree.
Domaines
Informatique [cs]Origine | Fichiers produits par l'(les) auteur(s) |
---|