Local 7-coloring for planar subgraphs of unit disk graphs
Theoretical Computer Science , Volume 412 - Issue 18 p. 1696- 1704
We study the problem of computing locally a coloring of an arbitrary planar subgraph of a unit disk graph. Each vertex knows its coordinates in the plane and can communicate directly with all its neighbors within unit distance. Using this setting, first a simple algorithm is given whereby each vertex can compute its color in a 9-coloring of the planar graph using only information on the subgraph located within at most 9 hops away from it in the original unit disk graph. A more complicated algorithm is then presented whereby each vertex can compute its color in a 7-coloring of the planar graph using only information on the subgraph located within a constant number (201, to be exact) of hops away from it.
|, , ,|
|Theoretical Computer Science|
|Organisation||School of Computer Science|
Czyzowicz, J., Dobrev, S., Gonzlez-Aguilar, H., Kralovic, R., Kranakis, E, Opatrny, J., … Urrutia, J. (2011). Local 7-coloring for planar subgraphs of unit disk graphs. In Theoretical Computer Science (Vol. 412, pp. 1696–1704). doi:10.1016/j.tcs.2010.12.044