On Generalisations of the AVD Conjecture to Digraphs

Julien Bensmail (1) , Fionn Mc Inerney (2)

1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
2 ACRO - Algorithmique, Combinatoire et Recherche Opérationnelle

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.

Mots clés: Digraphs; AVD Conjecture; Proper edge-colourings; proper edge-colourings; digraphs

Domaines: Mathématique discrète [cs.DM]

Julien Bensmail, Fionn Mc Inerney. On Generalisations of the AVD Conjecture to Digraphs. Graphs and Combinatorics, 2021, 37, pp.545-558. ⟨10.1007/s00373-020-02263-9⟩. ⟨hal-02613858v2⟩