Publication Name On Coloring the Square of Unit Disk Graph  
Publication Type Technical Report  
Publication Date December, 2006  
Bibliography Entry Tiegeng Ren, Kevin L. Bryan, and Lubos Thoma, On Coloring the Square of Unit Disk Graph, University of Rhode Island, Technical Report, TR06-316, December 2006  
Download Publication downloads/colors.pdf  
A graph G is a Unit Disk (UD) graph if there is an assignment of unit disks centered at its vertices such that there is an edge in G iff the corresponding unit disks intersect. The square G² of G is defined as a graph on the same vertex set as G and having edges between pairs of vertices with graph distance at most two in G. Our results on the chromatic number of G² are motivated by an application for wireless sensor networks. Namely, if G, an UD, is an underlying graph of a wireless sensor network, the square of G² reflects possible conflicts in transmission between sensors in the network. An upper bound on the chromatic number of G² implies directly an upper bound on the frame length in the Time Division Multi-Allocation (TDMA) used for transmission scheduling in the sensor network. The main result of the present paper shows that the chromatic number of G² is linear in ω(G) and is at most 13 ω(G), where ω(G) is the indepen- dence number of G. We also present an effcient algorithm to find a coloring corresponding to the upper bound.

Copyright © 2005. All rights reserved.
Department Of Computer Science and Statistics
Univeristy Of Rhode Island