ABSTRACT
We study deterministic, distributed algorithms for two weak variants of the standard graph coloring problem. We consider defective colorings, i.e., colorings where nodes of a color class may induce a graph of maximum degree d for some parameter d>0. We also look at colorings where a minimum number of multi-chromatic edges is required. For an integer k>0, we call a coloring k-partially proper if every node v has at least min{k,deg(v)} neighbors with a different color. We show that for all d∈{1,...,Δ}, it is possible to compute a O(Δ2/d2)-coloring with defect d in time O(log*n) where Δ is the largest degree of the network graph. Similarly, for all k∈{1,...,Δ}, a k-partially proper O(k2)-coloring can be computed in O(log*n) rounds.
As an application of our weak defective coloring algorithm, we obtain a faster deterministic algorithm for the standard vertex coloring problem on graphs with moderate degrees. We show that in time O(Δ+log*n), a (Δ+1)-coloring can be computed, a task for which the best previous algorithm required time O(Δ*log(Δ) + log*n). The same result holds for the problem of computing a maximal independent set.
- J. Andrews and M. Jacobson. On a generalization of chromatic number. Congressus Numerantium, 47:33--48, 1985.Google Scholar
- B. Awerbuch. Complexity of network synchronization. Journal of the ACM, 32(4):804--823, 1985. Google ScholarDigital Library
- B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin. Network decomposition and locality in distributed computation. In Proc. of 30th Symposium on Foundations of Computer Science (FOCS), pages 364--369, 1989. Google ScholarDigital Library
- L. Barenboim and M. Elkin. Sublogarithmic distributed mis algorithm for sparse graphs using nash-williams decomposition. In Proc. of 27th ACM Symposium on Principles of Distributed Computing (PODC), 2008. Google ScholarDigital Library
- L. Barenboim and M. Elkin. Distributed (Δ+1)-coloring in linear (in Δ) time. In Proc. of the 41st ACM Symposium on Theory of Computing (STOC), 2009. Google ScholarDigital Library
- R. Cole and U. Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 70(1):32--53, 1986. Google ScholarDigital Library
- L. Cowen, R. Cowen, and D. Woodall. Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valence. Journal of Graph Theory, 10:187--195, 1986.Google ScholarCross Ref
- L. Cowen, W. Goddard, and C. Jesurum. Defective coloring revisitied. Journal of Graph Theory, 24(3):205--219, 1997. Google ScholarDigital Library
- G. De Marco and A. Pelc. Fast distributed graph coloring with O(Δ) colors. In Proc. of 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 630--635, 2001. Google ScholarDigital Library
- P. Erdős, P. Frankl, and Z. Füredi. Families of finite sets in which no set is covered by the union of r others. Israel Journal of Mathematics, 51:79--89, 1985.Google ScholarCross Ref
- M. Frick. A survery of (m,k)-colorings. Annals of Discrete Mathematics, 55:45--58, 1993.Google ScholarCross Ref
- A. Goldberg, S. Plotkin, and G. Shannon. Parallel symmetry-breaking in sparse graphs. SIAM Journal on Discrete Mathematics, 1(4):434--446, 1988. Google ScholarDigital Library
- F. Harary and K. Jones. Conditional colorability II: Bipartite variations. Congressus Numerantium, 50:205--218, 1985.Google Scholar
- K. Kothapalli, M. Onus, C. Scheideler, and C. Schindelhauer. Distributed coloring in o(√log n) bit rounds. In Proc. of 20th IEEE Int. Parallel and Distributed Processing Symposium (IPDPS), 2006. Google ScholarDigital Library
- F. Kuhn. Local multicoloring algorithms: Computing a nearly-optimal TDMA schedule in constant time. In Proc. of 26th Symp. on Theoretical Aspects of Computer Science (STACS), 2009.Google Scholar
- F. Kuhn and R. Wattenhofer. On the complexity of distributed graph coloring. In Proc. of 25th ACM Symposium on Principles of Distributed Computing (PODC), pages 7--15, 2006. Google ScholarDigital Library
- N. Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193--201, 1992. Google ScholarDigital Library
- L. Lovász. On decompositions of graphs. Studia Sci. Math. Hungar., 1:237--238, 1966.Google Scholar
- M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 15:1036--1053, 1986. Google ScholarDigital Library
- M. Naor and L. Stockmeyer. What can be computed locally? In Proc. of 25th ACM Symposium on Theory of Computing (STOC), pages 184--193, 1993. Google ScholarDigital Library
- A. Panconesi and A. Srinivasan. On the complexity of distributed network decomposition. Journal of Algorithms, 20(2):581--592, 1995. Google ScholarDigital Library
- A. Pelc. Personal communication.Google Scholar
- J. Schneider and R. Wattenhofer. A log-star distributed maximal independent set algorithm for growth-bounded graphs. In Proc. of 27th ACM Symposium on Principles of Distributed Computing (PODC), 2008. Google ScholarDigital Library
- M. Szegedy and S. Vishwanathan. Locality based graph coloring. In Proc. of the 25th ACM Symposium on Theory of Computing (STOC), pages 201--207, 1993. Google ScholarDigital Library
- D. Woodall. Improper colourings of graphs. In R. Nelson and R. Wilson, editors, Graph Colourings. Longman Scientific and Technical, 1990.Google Scholar
Index Terms
Weak graph colorings: distributed algorithms and applications
Recommendations
On the complexity of distributed graph coloring
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computingColoring the nodes of a graph with a small number of colors is one of the most fundamental problems in theoretical computer science. In this paper, we study graph coloring in a distributed setting. Processors of a distributed system are nodes of an ...
Cut-Colorings in Coloring Graphs
This paper studies the connectivity and biconnectivity of coloring graphs. For $$k\in \mathbb {N}$$k?N, the k-coloring graph of a base graph G has vertex set consisting of the proper k-colorings of G and edge set consisting of the pairs of k-colorings ...
Injective colorings of planar graphs with few colors
An injective coloring of a graph is a vertex coloring where two vertices have distinct colors if a path of length two exists between them. In this paper some results on injective colorings of planar graphs with few colors are presented. We show that all ...
Comments