Orthogonal Colourings of Random Geometric Graphs

Abstract

In this paper, we study orthogonal colourings of random geometric graphs. Two colourings of a graph are orthogonal if they have the property that when two vertices receive the same colour in one colouring, then those vertices receive distinct colours in the other colouring. A random geometric graph $RG(n,r)$ is a graph constructed by randomly placing $n$ vertices in the unit square and connecting two vertices with an edge if and only if their distance is less than the threshold $r$. We show first that random geometric graphs with $r>n^{-\alpha }$, where $0\le \alpha \le \frac{1}{4}$, have an orthogonal colouring using $n^{1-2\alpha }(1+o(1))$ colours with high probability. Then, we show for an infinite number of values of $n$, random geometric graphs with threshold $r<c{n}^{-\frac{1}{4}}$, $c<1$, have an optimal orthogonal colouring with high probability. We obtain both of these results by constructing orthogonal colourings of the clique grid graph.

16 pages, 2 figures