The Distant-l Chromatic Number of Random Geometric Graphs

Yilun Shang

paper

The Distant-l Chromatic Number of Random Geometric Graphs

arXiv:0909.3678

Abstract

A random geometric graph $G_{n}$ is given by picking $n$ vertices in $R^{d}$ independently under a common bounded probability distribution, with two vertices adjacent if and only if their $l^{p}$ -distance is at most $r_{n}$ . We investigate the distant- $l$ chromatic number $χ_{l} (G_{n})$ of $G_{n}$ for $l \geq 1$ . Complete picture of the ratios of $χ_{l} (G_{n})$ to the chromatic number $χ (G_{n})$ are given in the sense of almost sure convergence.

7 pages 1 figure