Milan Bradonjic ; Tobias Mueller ; Allon G. Percus - Coloring Geographical Threshold Graphs

dmtcs:497 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, Vol. 12 no. 3 -
Coloring Geographical Threshold GraphsArticle

Authors: Milan Bradonjic 1; Tobias Mueller 2; Allon G. Percus 3

  • 1 Theoretical Division and Center for Nonlinear Studies
  • 2 School of Mathematical Sciences [Tel Aviv]
  • 3 School of Mathematical Science [Claremont]

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: chi = 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.

Volume: Vol. 12 no. 3
Section: Graph and Algorithms
Published on: January 1, 2010
Imported on: March 26, 2015
Keywords: Geographical threshold graphs,random geometric graphs,chromatic number,coloring algorithm,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
    Source : OpenAIRE Graph
  • EMT/MISC: Collaborative Research: Harnessing Statistical Physics for Computing and Communication; Funder: National Science Foundation; Code: 0829945

Consultation statistics

This page has been seen 342 times.
This article's PDF has been downloaded 299 times.