ID:21357
Type of Publication: Journal Articles
Authors: Josep.Diaz, Zvi Lotker, Maria.Serna
Title: The distant-2 chromatic number of random proximity and random geometric graphs
Name of the Journal: Inf. Process. Lett. (Netherlands)
Year: 2008
Volume: 106
Issue: 4
Pages: 144 - 8
Abstract: We are interested in finding bounds for the distant-2 chromatic number of geometric graphs drawn from different models. We consider two undirected models of random graphs: random geometric graphs and random proximity graphs for which sharp connectivity thresholds have been shown. We are interested in a.a.s. connected graphs close just above the connectivity threshold. For such subfamilies of random graphs we show that the distant-2-chromatic number is Θ(log n) with high probability. The result on random geometric graphs is extended to the random sector graphs defined in [J. Diaz, J. Petit, M. Serna. A random graph model for optical networks of sensors, IEEE Transactions on Mobile Computing 2 (2003) 143-154]. [All rights reserved Elsevier].
Keywords: geometry;graph colouring;probability;random processes; ,
Url: http://dx.doi.org/10.1016/j.ipl.2007.10.015
Last Updated: 9/15/2008 12:00:00 AM
Powered by Rami Palombo © 2005
Search in: Google Scholar  |  Scitation