Orthogonal Colourings of Random Geometric Graphs

arXiv2303.08211MaRDI QIDQ6429601FDOQ6429601

Authors: Jeannette Janssen, Kyle MacKeigan 

Publication date: 14 March 2023

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 $0leqalphaleqfrac14$, have an orthogonal colouring using $n^{1-2alpha}(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}^{-frac14}$, $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.

This page was built for publication: Orthogonal Colourings of Random Geometric Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6429601)