## Abstract

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}) ≠ 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, 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.

Original language | English (US) |
---|---|

Pages (from-to) | 173-191 |

Number of pages | 19 |

Journal | Combinatorics Probability and Computing |

Volume | 16 |

Issue number | 2 |

DOIs | |

State | Published - Mar 2007 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics