Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-08T22:00:11.886Z Has data issue: false hasContentIssue false
  • English
  • Français

Edge Colouring with Delays

Published online by Cambridge University Press:  01 March 2007

NOGA ALON  and
VERA ASODI
NOGA ALON
Affiliation:
Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel (e-mail: nogaa@post.tau.ac.il)
VERA ASODI
Affiliation:
Department of Computer Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel (e-mail: veraa@post.tau.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 e1 and e2 with the same transmitter, f(e1) ≠ f(e2), and for every two edges e1 and e2 with the same receiver, f(e1) + c(e1) ≢ f(e2) + c(e2) (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 conjectureholds for some multigraphs, applying algebraic tools.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 2 , March 2007 , pp. 173 - 191
Copyright
Copyright © Cambridge University Press 2006

References

[1]Alon, N. (1991) A parallel algorithmic version of the Local Lemma. Random Struct. Alg. 2 367–378.CrossRefGoogle Scholar
[2]Alon, N. (1993) Restricted colorings of graphs. In Surveys in Combinatorics: Proc. 14th British Combinatorial Conference, London (Walker, K., ed.), Vol. 187 of Mathematical Society Lecture Notes Series, Cambridge University Press, pp. 1–33.CrossRefGoogle Scholar
[3]Alon, N. (1999) Combinatorial Nullstellensatz. Combin. Probab. Comput. 8 7–29.CrossRefGoogle Scholar
[4]Alon, N. and Spencer,, J. H. (2000) The Probabilistic Method, 2nd edn, Wiley.CrossRefGoogle Scholar
[5]Beck, J. (1991) An algorithmic approach to the Lovász Local Lemma. Random Struct. Alg. 2 343–365.Google Scholar
[6]Czumaj, A. and Scheideler, C. (2000) Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lovász Local Lemma. Random Struct. Alg. 17 213–237.Google Scholar
[7]Ellingham, M. N. and Goddyn, L. (1996) List edge colourings of some 1-factorable multigraphs. Combinatorica 16 343–352.CrossRefGoogle Scholar
[8]Häggkvist, R. and Janssen, J. (1997) New bounds on the list chromatic index of the complete graph and other simple graphs. Combin. Probab. Comput. 6 273–295.Google Scholar
[9]Hall, M. (1952) A combinatorial problem on abelian groups. Proc. Amer. Math. Soc. 3 584–587.Google Scholar
[10]Haxell, P. E. (2001) A note on vertex list colouring. Combin. Probab. Comput. 10 345–348.CrossRefGoogle Scholar
[11]Haxell, P. E., Wilfong, G. T. and Winkler, P. Delay coloring and optical networks. To appear.Google Scholar
[12]Kahn, J. (1996) Asymptotically good list-colorings. J. Combin. Theory Ser. A 73 1–59.Google Scholar
[13]Molloy, M. and Reed, B. (1998) Further algorithmic aspects of the Local Lemma. In Proc. 30th Annual ACM Symposium on Theory of Computing, pp. 524–529.CrossRefGoogle Scholar
[14]Molloy, M. and Reed, B. (2000) Near-optimal list colorings. Random Struct. Alg. 17 376–402.Google Scholar
[15]Molloy, M. and Reed, B. (2001) Graph Colouring and the Probabilistic Method, Springer.Google Scholar
[16]Reed, B. (1999) The list colouring constants. J. Graph Theory 31 149–153.3.0.CO;2-#>CrossRefGoogle Scholar
[17]Reed, B. and Sudakov, B. (2002) Asymptotically the list colouring constants are 1. J. Combin. Theory Ser. B 86 27–37.Google Scholar
[18]Ross, K., Bambos, N., Kumaran, K., Saniee, I. and Widjaja, I. (2003) Scheduling bursts in time-domain wavelength interleaved networks. IEEE JSAC OCN 21 1441–1451.Google Scholar
[19]Widjaja, I., Saniee, I., Giles, R. and Mitra, D. (2003) Light core and intelligent edge for a flexible, thin-layered and cost-effective optical transport network. IEEE Optical Communications 1(2); IEEE Communications Magazine 45(5) 31–36.Google Scholar