Name
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 @Q(logn) 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]. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.ipl.2007.10.015 | Inf. Process. Lett. |
Keywords | Field | DocType |
random graph,random geometric graph,j. petit,random sector graph,random graph model,connectivity threshold,distant-2 chromatic number,j. diaz,graph problems,geometric graph,coloring,distant-2 coloring,random graphs,random proximity graph,connected graph | Random regular graph,Discrete mathematics,Indifference graph,Combinatorics,Random graph,Chordal graph,Clique-sum,Pathwidth,1-planar graph,Mathematics,Maximal independent set | Journal |
Volume | Issue | ISSN |
106 | 4 | 0020-0190 |
Citations | PageRank | References |
2 | 0.37 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Josep Díaz | 1 | 489 | 204.59 |
| Zvi Lotker | 2 | 1000 | 79.68 |
| Maria Serna | 3 | 216 | 18.19 |