Coloring Geographical Threshold Graphs

The Sixth Workshop on Analytic Algorithmics and Combinatorics

Milan Bradonjic ; Tobias Mu ; ller† Allon G. Percus

Others  :  http://www.siam.org/proceedings/analco/2009/anl09_002_bradonjicm.pdf
PID  :  18277

来源: CEUR

【 摘 要 】

We propose a coloring algorithm for sparse random graphsgenerated by the geographical threshold graph (GTG)model, a generalization of random geometric graphs (RGG).In a GTG, nodes are distributed in a Euclidean space, andedges are assigned according to a threshold function involv-ing the distance between nodes as well as randomly chosennode weights. The motivation for analyzing this model isthat many real networks (e.g., wireless networks, the Inter-net, etc.) need to be studied by using a “richer” stochasticmodel (which in this case includes both a distance betweennodes and weights on the nodes). Here, we analyze the GTGcoloring algorithm together with the graph’s clique number,showing formally that in spite of the differences in structurebetween GTG and RGG, the asymptotic behavior of thechromatic number is identical: χ = lnnln lnn (1+ o(1)). Finally,we consider the leading corrections to this expression, againusing the coloring algorithm and clique number to providebounds on the chromatic number. We show that the gap be-tween the lower and upper bound is within C lnn/(ln lnn)2,