On Generalisations of the AVD Conjecture to Digraphs

Description

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.

Abstract

International audience

Additional details