Coloring Geographical Threshold Graphs
Milan Bradonjić, Tobias Müller, Allon Percus
Abstract
We propose a coloring algorithm for sparse random graphs generated by
the geographical threshold graph (GTG) model, a generalization of
random geometric graphs (RGG). In a GTG, nodes are distributed in a
Euclidean space, and edges are assigned according to a threshold
function involving the distance between nodes as well as randomly
chosen node weights. The motivation for analyzing this model is that
many real networks (e.g., wireless networks, the Internet, etc.) need
to be studied by using a ``richer" stochastic model (which in this
case includes both a distance between nodes and weights on the
nodes). Here, we analyze the GTG coloring algorithm together with the
graph's clique number, showing formally that in spite of the
differences in structure between GTG and RGG, the asymptotic behavior
of the chromatic number is identical: χ= ln n /
ln ln n (1+o(1)). Finally, we consider the leading corrections
to this expression, again using the coloring algorithm and clique
number to provide bounds on the chromatic number. We show that the gap
between the lower and upper bound is within C ln n/(ln ln
n)2, and specify the constant C.
Full Text: PDF PostScript