×

Local 7-coloring for planar subgraphs of unit disk graphs. (English) Zbl 1216.05155

Summary: 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.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bose, P.; Morin, P.; Stojmenovic, I.; Urrutia, J., Routing with guaranteed delivery in ad hoc wireless networks, Wireless Networks, 7, 609-616 (2001) · Zbl 0996.68012
[2] Capkun, S.; Hamdi, M.; Hubeaux, J.-P., GPS-free positioning in mobile ad hoc networks, Cluster Computing, 5, 157-167 (2002)
[3] Caragiannis, I.; Fishkin, A. V.; Kaklamanis, C.; Papaioannou, E., A tight bound for online coloring of disk graphs, (Pelc, A.; Raynal, M., SIROCCO 2005, Mont Saint-Michel, France, May 24-26, 2005, Proceedings. SIROCCO 2005, Mont Saint-Michel, France, May 24-26, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3499 (2005), Springer), 78-88 · Zbl 1085.68598
[4] Chavez, E.; Dobrev, S.; Kranakis, E.; Opatrny, J.; Stacho, L.; Urrutia, J., Local construction of planar spanners in unit disk graphs with irregular transmission ranges, (Correa, M. K.j.; Hevia, A., Latin 06. Latin 06, Lecture Notes in Computer Science, vol. 3387 (2006), Springer Verlag), 286-297 · Zbl 1145.68472
[5] P. Dörre, Every planar graph is 4-colourable and 5-choosable a joint proof, Fachhochschule Südwestfalen, University of Applied Sciences, unpublished note.; P. Dörre, Every planar graph is 4-colourable and 5-choosable a joint proof, Fachhochschule Südwestfalen, University of Applied Sciences, unpublished note.
[6] Gabriel, K. R.; Sokal, R. R., A new statistical approach to geographic variation analysis, Systemic Zoology, 18, 259-278 (1972)
[7] Galinier, P.; Hertz, A., A survey of local search methods for graph coloring, Computers & OR, 33, 2547-2562 (2006) · Zbl 1086.90060
[8] Ghosh, S.; Karaata, M., A self-stabilizing algorithm for coloring planar graphs, Distributed Computing, 7, 55-59 (1993) · Zbl 0818.68089
[9] Gräf, A.; Stumpf, M.; Weißenfels, G., On coloring unit disk graphs, Algorithmica, 20, 3, 277-293 (1998) · Zbl 0901.68152
[10] Jensen, T. R.; Toft, B., (Graph Coloring Problems. Graph Coloring Problems, Wiley-Interscience Series in Discrete Mathematics and Optimization (1995), John Wiley & Sons)
[11] E. Kranakis, H. Singh, J. Urrutia, Compass routing on geometric networks, in: Proc. of 11th Canadian Conference on Computational Geometry, August 1999, pp. 51-54.; E. Kranakis, H. Singh, J. Urrutia, Compass routing on geometric networks, in: Proc. of 11th Canadian Conference on Computational Geometry, August 1999, pp. 51-54.
[12] Linial, N., Locality in distributed graph algorithms, SIAM Journal on Computing, 21, 1, 193-201 (1992) · Zbl 0787.05058
[13] Marathe, M. V.; Breu, H.; Hunt, H. B.; Ravi, S. S.; Rosenkrantz, D. J., Simple heuristics for unit disk graphs, Networks, 25, 1, 59-68 (1995) · Zbl 0821.90128
[14] Miyamoto, Y.; Matsui, T., Multicoloring unit disk graphs on triangular lattice points, (SODA (2005), SIAM), 895-896 · Zbl 1297.05089
[15] Peleg, D., Distributed Computing: A Locality-Sensitive Approach (2000), SIAM · Zbl 0959.68042
[16] N. Robertson, D.P. Sanders, P. Seymour, R. Thomas, Efficiently four-coloring planar graphs, in: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, May 1996, pp. 571-575.; N. Robertson, D.P. Sanders, P. Seymour, R. Thomas, Efficiently four-coloring planar graphs, in: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, May 1996, pp. 571-575. · Zbl 0917.05030
[17] M. Szegedy, S. Vishwanathan, Locality based graph coloring, in: Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, May 1993, pp. 201-207.; M. Szegedy, S. Vishwanathan, Locality based graph coloring, in: Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, May 1993, pp. 201-207. · Zbl 1310.05099
[18] Thomassen, C., Every planar graph is \(5\)-choosable, Combinatorial Theory Series B, 62, 1, 180-181 (1994) · Zbl 0805.05023
[19] Tuza, Z., Graph colorings with local constraints: a survey, Discussiones Mathematicae-Graph Theory, 17, 2, 161-228 (1997) · Zbl 0923.05027
[20] Tuza, Z.; Voigt, M., A note on planar 5-list colouring: non-extendability at distance 4, Discrete Mathematics, 251, 1, 169-172 (2002) · Zbl 1002.05020
[21] Urrutia, J., Local solutions for global problems in wireless networks, Journal of Discrete Algorithms, 5, 3, 395-407 (2007) · Zbl 1130.05059
[22] Voigt, M., List colourings of planar graphs, Discrete Mathematics, 120, 1-3, 215-219 (1993) · Zbl 0790.05030
[23] Vredeveld, T.; Lenstra, J. K., On local search for the generalized graph coloring problem, Operations Research Letters, 31, 1, 28-34 (2003) · Zbl 1013.90071
[24] Y. Wang, X.-Y. Li, Localized construction of bounded degree and planar spanner for wireless ad hoc networks, in: DialM: Proceedings of the Discrete Algorithms and Methods for Mobile Computing & Communications, 2003.; Y. Wang, X.-Y. Li, Localized construction of bounded degree and planar spanner for wireless ad hoc networks, in: DialM: Proceedings of the Discrete Algorithms and Methods for Mobile Computing & Communications, 2003.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.