The chromatic and clique numbers of random scaled sector graphs

Random scaled sector graphs were introduced as a generalization of random geometric graphs to model networks of sensors using optical communication. In the random scaled sector graph model vertices are placed uniformly at random into the [0,1]2 unit square. Each vertex i is assigned uniformly at random sector Si, of central angle αi, in a circle of radius ri (with vertex i as the origin). An arc is present from vertex i to any vertex j, if j falls in Si. In this work, we study the value of the chromatic number χ(Gn), directed clique number ω(Gn), and undirected clique number ω2^(Gn) for random scaled sector graphs with n vertices, where each vertex spans a sector of α degrees with radius rn=lnnn. We prove that for values α<π, as n→∞ w.h.p., χ(Gn) and ω2^(Gn) are Θ(lnnlnlnn), while ω(Gn) is O(1), showing a clear difference with the random geometric graph model. For α>π w.h.p., χ(Gn) and ω2^(Gn) are Θ(lnn), being the same for random scaled sector and random geometric graphs, while ω(Gn) is Θ(lnnlnlnn).