Edge colouring with delays

Consider the following communication problem, which leads to a new notion of edge colouring. The communication network is represented by a bipartite multigraph, where the nodes on one side are the transmitters and the nodes on the other side are the receivers. The edges correspond to messages, and every edge e is associated with an integer c(e), corresponding to the time it takes the message to reach its destination. A proper k-edge-colouring with delays is a function f from the edges to {0,1,..., k - 1}, such that, for every two edges e₁ and e₂ with the same transmitter, f(e₁) ≠ f(e₂), and for every two edges e₁ and e₂ with the same receiver, f(e₁) + c(e₁) ≢ + f(e ₂) + c(e₂) (mod k). Ross, Bambos, Kumaran, Saniee and Widjaja [18] conjectured that there always exists a proper edge colouring with delays using k = Δ + o(Δ) colours, where Δ is the maximum degree of the graph. Haxell, Wilfong and Winkler [11] conjectured that a stronger result holds: k = Δ + 1 colours always suffice. We prove the weaker conjecture for simple bipartite graphs, using a probabilistic approach, and further show that the stronger conjecture holds for some multigraphs, applying algebraic tools.