From Wikipedia, the free encyclopedia
The figure on the right shows a weak 2-coloring of a graph. Each dark vertex (color 1) is adjacent to at least one light vertex (color 2) and vice versa.
A graph vertex coloring is a weak coloring, but not necessarily vice versa.
Every graph has a weak 2-coloring. The figure on the right illustrates a simple algorithm for constructing a weak 2-coloring in an arbitrary graph. Part (a) shows the original graph. Part (b) shows a breadth-first search tree of the same graph. Part (c) shows how to color the tree: starting from the root, the layers of the tree are colored alternatingly with colors 1 (dark) and 2 (light).
If there is no isolated vertex in the graph G, then a weak 2-coloring determines a domatic partition: the set of the nodes with c(v) = 1 is a dominating set, and the set of the nodes with c(v) = 2 is another dominating set.
Historically, weak coloring served as the first non-trivial example of a graph problem that can be solved with a local algorithm (a distributed algorithm that runs in a constant number of synchronous communication rounds). More precisely, if the degree of each node is odd and bounded by a constant, then there is a constant-time distributed algorithm for weak 2-coloring.
This is different from (non-weak) vertex coloring: there is no constant-time distributed algorithm for vertex coloring; the best possible algorithms require O(log* |V|) communication rounds. Here log* x is the iterated logarithm of x.
- ^ a b Moni Naor and Larry Stockmeyer: "What can be computed locally?", SIAM Journal on Computing 24:6(1995), p. 1259-1277.
- ^ Nathan Linial: "Locality in distributed graph algorithms", SIAM Journal on Computing 21:1(1992), p. 193-201.
- ^ Richard Cole and Uzi Vishkin: "Deterministic coin tossing with applications to optimal parallel list ranking", Information and Control 70:1(1986), p. 32-53.
|This combinatorics-related article is a stub. You can help Wikipedia by expanding it.|