The Distant-l Chromatic Number of Random Geometric Graphs

2009/09/21 by Shang, Yilun
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.0909.3678

Abstract

A random geometric graph G_n is given by picking n vertices in ℝ^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≥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.

Related

• Clique colourings of geometric graphs
• Topology and chromatic number of random ε-distance graphs on spheres
• On the relation between graph distance and Euclidean distance in random geometric graphs
• Local convergence of random graph colorings
• The Total Acquisition Number of Random Geometric Graphs