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(1) and e(2) with the same transmitter, f(e(1)) not equal f(e(2)), and for every two edges e(1) and e(2) with the same receiver, f(e(1)) + c(e(1)) + f(e(2)) + c(e(2)) (mod k). Ross, Bambos, Kumaran, Saniec and Widjaja [18] conjectured that there always exists a proper edge colouring with delays using k = Delta + o(Delta) colours, where Delta is the maximum degree of the graph. Haxell, Wilfong and Winkler [11] conjectured that a stronger result holds: k = Delta + 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.