Pré-Publication, Document De Travail Année : 2025

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.
Fichier principal
Vignette du fichier
snsd.pdf (460) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04947954 , version 1 (14-02-2025)

Identifiants

  • HAL Id : hal-04947954 , version 1

Citer

Julien Bensmail, Leandro Montero. NSD Edge-Colourings with Strong Assignment Constraints. 2025. ⟨hal-04947954⟩
0 Consultations
0 Téléchargements

Partager

More