On Generalisations of the AVD Conjecture to Digraphs - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2020

On Generalisations of the AVD Conjecture to Digraphs

Résumé

Given an undirected graph, in the AVD (edge-colouring) Conjecture, the goal is to find a proper edge-colouring with the least number of colours such that every two adjacent vertices are incident to different sets of colours. More precisely, the conjecture says that, a few exceptions apart, every graph G should admit such an edge-colouring with at most ∆(G)+2 colours. Several aspects of interest behind this problem have been investigated over the recent years, including verifications of the conjecture for particular graph classes, general approximations of the conjecture, and multiple generalisations. In this paper, following a recent work of Sopena and Woźniak, generalisations of the AVD Conjecture to digraphs are investigated. More precisely, four of the several possible ways of generalising the conjecture are focused upon. We completely settle one of our four variants, while, for the three remaining ones, we provide partial results.
Fichier principal
Vignette du fichier
avd-directed.pdf (358.91 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02613858 , version 1 (20-05-2020)
hal-02613858 , version 2 (30-10-2020)
hal-02613858 , version 3 (21-02-2022)

Identifiants

  • HAL Id : hal-02613858 , version 1

Citer

Julien Bensmail, Fionn Mc Inerney. On Generalisations of the AVD Conjecture to Digraphs. [Research Report] Université côte d'azur; Aix-Marseile Université. 2020. ⟨hal-02613858v1⟩

Collections

LARA
301 Consultations
347 Téléchargements

Partager

Gmail Facebook X LinkedIn More