Wilfong–Haxell–Winkler delay-colouring conjecture for bipartite multigraphs

Let GG be a bipartite multigraph with partition classes A,BA,B and maximum degree dd. Each edge ee has an associated integer delay r(e)r(e). An edge-colouring is a map f:E(G){0,,d}f:E(G)\to\{0,\ldots,d\}, and f+r(modd+1)f+r\pmod{d+1} is defined on an edge ee as f(e)+r(e)(modd+1)f(e)+r(e)\pmod{d+1}. Wilfong–Haxell–Winkler's delay-colouring conjecture. The graph GG admits an edge-colouring ff such that ff is proper on AA and f+r(modd+1)f+r\pmod{d+1} is proper on BB. This conjecture is motivated by scheduling in optical networks and is proved in the paper in the special case d=3d=3; the general case remains open.

Sources & referencesView supporting material

Primary source

Agelos Georgakopoulos, “Delay colourings of cubic graphs”, arXiv:1211.1306 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.